#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi20/d2/debug.h"
#else
#define debug(...) void(37)
#endif
long long count_tastiness(long long X, std::vector<long long> A) {
int K = 60;
A.resize(60);
for (int i = 0; i < K - 1; ++i) {
long long carry = max(0LL, (A[i] - X) / 2);
A[i] -= 2 * carry;
A[i + 1] += carry;
}
A.back() = min(A.back(), X);
debug(A);
vector<vector<long long>> ways(K, vector<long long>(K));
for (int i = K - 1; i >= 0; --i) {
if (A[i] >= X) {
continue;
}
debug(i);
vector<long long> states;
states.push_back((1LL << i) * X);
for (int j = i; j >= 0; --j) {
debug(j, states);
vector<long long> new_states;
for (auto x : states) {
long long dec = (1LL << j) * A[j];
if (dec >= x) {
ways[i][j] += 1;
dec -= x;
if (true) {
new_states.push_back((2LL << j) * X - dec);
}
if (dec == (1LL << j) * X) {
//assert(dec == (1LL << j));
ways[i][j] += 1;
} else {
new_states.push_back((1LL << j) * X - dec);
}
} else {
new_states.push_back(x - dec);
}
}
swap(states, new_states);
}
}
debug(ways);
vector<long long> dp(K);
long long prev = 1;
for (int i = K - 1; i >= 0; --i) {
debug(prev, dp);
if (A[i] >= X) {
prev = prev * 2 + dp[i];
continue;
}
for (int j = i; j >= 0; --j) {
dp[j] += prev * ways[i][j];
}
prev += dp[i];
}
debug(prev);
return prev;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1091 ms |
779024 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1112 ms |
799396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1091 ms |
786548 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1091 ms |
779024 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |