-
Notifications
You must be signed in to change notification settings - Fork 2
/
Solution.java
79 lines (68 loc) · 1.75 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package com.algorithm.playground.google.kickstart._2019.b.task2;
import java.util.Arrays;
import java.util.Scanner;
/**
* https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050eda/00000000001198c3
*/
public class Solution {
private static int[][] cache;
public static void main(String[] args) {
try (Scanner console = new Scanner(System.in)) {
int tests = console.nextInt();
for (int test = 1; test <= tests; test++) {
Stone[] stones = new Stone[console.nextInt()];
int wallTime = 0;
for (int i = 0; i < stones.length; i++) {
stones[i] = new Stone(console.nextInt(), console.nextInt(), console.nextInt());
wallTime += stones[i].s;
}
cache = new int[wallTime][stones.length];
for (int[] row : cache) {
Arrays.fill(row, -1);
}
int ans = solve(stones);
System.out.println(String.format("Case #%s: %s", test, ans));
}
}
}
private static int solve(Stone[] stones) {
Arrays.sort(stones, (s1, s2) -> s1.s * s2.l - s2.s * s1.l);
return dp(stones, 0, 0);
}
private static int dp(Stone[] stones, int time, int i) {
if (i == stones.length) {
return 0;
} else if (cache[time][i] != -1) {
return cache[time][i];
} else {
Stone s = stones[i];
int energy = Math.max(0, s.e - s.l * time);
int max;
if (energy == 0) {
max = dp(stones, time, i + 1);
} else {
max = Math.max(
dp(stones, time + s.s, i + 1) + energy,
dp(stones, time, i + 1)
);
}
return cache[time][i] = max;
}
}
private static class Stone {
private int s, e, l;
private Stone(int s, int e, int l) {
this.s = s;
this.e = e;
this.l = l;
}
@Override
public String toString() {
return "Stone{" +
"s=" + s +
", e=" + e +
", l=" + l +
'}';
}
}
}