This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "biscuits.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
ll count_tastiness(ll x, vl a) {
int k = 60;
while (a.size() < k) a.pb(0);
// if (x <= 10000) {
// rep(i, k) {
// if (a[i] > x) {
// ll l = (a[i] - x) / 2;
// a[i] -= l * 2;
// a[i + 1] += l;
// }
// }
// int mx = x + 10;
// vvl dp(k + 1, vl(mx));
// dp[0][0] = 1;
// rep(i, k) rep(j, mx) {
// ll now = dp[i][j];
// if (!now) continue;
// dp[i + 1][(j + a[i]) / 2] += now;
// if (j + a[i] >= x) dp[i + 1][(j + a[i] - x) / 2] += now;
// }
// rep2(i, 1, mx) assert(dp[k][i] == 0);
// return dp[k][0];
// } else {
vl lim(k);
rep(i, k - 1) {
lim[i + 1] = lim[i] / 2 + a[i];
}
ll ans = 0;
auto dfs = [&](auto &dfs, int i, ll j) -> void {
if (i < 0) {
if (!j) ans++;
return;
}
rep(l, 2) {
ll nj = j + l * x;
nj = max(nj - a[i], 0LL);
nj *= 2;
if (nj > lim[i]) break;
dfs(dfs, i - 1, nj);
}
};
dfs(dfs, k - 1, 0);
return ans;
// }
}
Compilation message (stderr)
biscuits.cpp: In function 'll count_tastiness(ll, vl)':
biscuits.cpp:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
43 | while (a.size() < k) a.pb(0);
| ~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |