import java.util.HashMap;
public class biscuits {
long count_tastiness(long x, long[] a) {
if (x == 1) {
return solveXIsOne(a);
}
return countNaive(x, a);
}
// How many diff. sums can we get by (n[i] * 2^i, where 0 <= n[i] <= a[i]).
long solveXIsOne(long[] a) {
return recursiveXIsOne(0, a[0], a);
}
HashMap<String, Long> map = new HashMap<>();
String toKey(int pos, long first) {
return pos + "." + first;
}
long recursiveXIsOne(int pos, long first, long[] a) {
if (pos == a.length - 1) {
return first + 1;
}
String key = toKey(pos, first);
if (map.containsKey(key)) map.get(key);
long res = recursiveXIsOne(pos + 1, a[pos + 1] + first / 2, a);
if (first > 0) {
res += recursiveXIsOne(pos + 1, a[pos + 1] + (first - 1) / 2, a);
}
map.put(key, res);
return res;
}
long countNaive(long x, long[] a) {
return countRec(x, a, 0);
}
long countRec(long x, long[] a, int index) {
if (index == a.length - 1) {
return a[a.length - 1] / x + 1;
}
long temp = a[index + 1];
a[index + 1] = a[index + 1] + a[index] / 2;
long answer = countRec(x, a, index + 1);
if (a[index] >= x) {
a[index + 1] = temp + (a[index] - x) / 2;
answer += countRec(x, a, index + 1);
a[index + 1] = temp;
}
a[index + 1] = temp;
return answer;
}
}
// (s[k-1] - i * X) / (2^(k-1)), 0 <= i < 2^(k - 1).
// For which i is this state valid?
// If for each position b s.t. b-th bit is set in i, (s[b+1] - (2^b + prev(i,b))X) / 2^(b+1) >= X.
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
10620 KB |
Output is correct |
2 |
Correct |
89 ms |
10236 KB |
Output is correct |
3 |
Correct |
85 ms |
10340 KB |
Output is correct |
4 |
Correct |
86 ms |
10344 KB |
Output is correct |
5 |
Correct |
84 ms |
10400 KB |
Output is correct |
6 |
Correct |
103 ms |
10600 KB |
Output is correct |
7 |
Correct |
85 ms |
10360 KB |
Output is correct |
8 |
Correct |
108 ms |
10936 KB |
Output is correct |
9 |
Correct |
91 ms |
10132 KB |
Output is correct |
10 |
Correct |
86 ms |
10252 KB |
Output is correct |
11 |
Correct |
86 ms |
10228 KB |
Output is correct |
12 |
Correct |
123 ms |
10760 KB |
Output is correct |
13 |
Correct |
111 ms |
10744 KB |
Output is correct |
14 |
Correct |
98 ms |
10728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
91 ms |
10488 KB |
Output is correct |
2 |
Execution timed out |
1032 ms |
94468 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
10344 KB |
Output is correct |
2 |
Correct |
86 ms |
10324 KB |
Output is correct |
3 |
Correct |
87 ms |
10472 KB |
Output is correct |
4 |
Execution timed out |
1200 ms |
103616 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
10744 KB |
Output is correct |
2 |
Execution timed out |
1105 ms |
11384 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
10620 KB |
Output is correct |
2 |
Correct |
89 ms |
10236 KB |
Output is correct |
3 |
Correct |
85 ms |
10340 KB |
Output is correct |
4 |
Correct |
86 ms |
10344 KB |
Output is correct |
5 |
Correct |
84 ms |
10400 KB |
Output is correct |
6 |
Correct |
103 ms |
10600 KB |
Output is correct |
7 |
Correct |
85 ms |
10360 KB |
Output is correct |
8 |
Correct |
108 ms |
10936 KB |
Output is correct |
9 |
Correct |
91 ms |
10132 KB |
Output is correct |
10 |
Correct |
86 ms |
10252 KB |
Output is correct |
11 |
Correct |
86 ms |
10228 KB |
Output is correct |
12 |
Correct |
123 ms |
10760 KB |
Output is correct |
13 |
Correct |
111 ms |
10744 KB |
Output is correct |
14 |
Correct |
98 ms |
10728 KB |
Output is correct |
15 |
Correct |
91 ms |
10488 KB |
Output is correct |
16 |
Execution timed out |
1032 ms |
94468 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |