#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int nmax = 60 + 2;
int k = 0;
vector<ll> a;
vector<ll> nxt;
ll x;
unordered_map<ll, ll, custom_hash> dp[nmax];
ll bkt(int p, int accum) {
if(p > k && accum < x) return 1;
if(dp[p].count(accum)) return dp[p][accum];
return dp[p][accum] = bkt(p + 1, (a[p] + accum) / 2) + (a[p] + accum >= x? bkt(p + 1, (a[p] + accum - x) / 2) : 0);
}
ll basedkt(int p, int limit) {
if(p == -1) return 1;
limit = min({limit, (1LL << p + 1) - 1, a[p]});
if(dp[p].count(limit)) return dp[p][limit];
if((1LL << p) <= limit) dp[p][limit] += basedkt(p - 1, limit - (1LL << p));
dp[p][limit] += basedkt(p - 1, limit);
return dp[p][limit];
}
long long count_tastiness(long long XXX, std::vector<long long> AAA) {
x = XXX;
a = AAA;
k = sz(a);
while(sz(a) < nmax) a.emplace_back(0);
int prv = nmax;
nxt.resize(nmax);
auto tmp = a;
for(int i = 0; i < sz(a); i++) {
a[i] *= (1LL << i);
}
for(int i = 1; i < sz(a); i++) a[i] += a[i - 1];
for(auto &b : a) b /= x;
for(int i = 0; i < nmax; i++) dp[i].clear();
int val = a.back();
return basedkt(sz(a) - 1, a.back());
}
#undef int
/**
Anul asta se da centroid.
-- Surse oficiale
*/
Compilation message
biscuits.cpp: In function 'll basedkt(ll, ll)':
biscuits.cpp:48:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
48 | limit = min({limit, (1LL << p + 1) - 1, a[p]});
| ~~^~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:60:7: warning: unused variable 'prv' [-Wunused-variable]
60 | int prv = nmax;
| ^~~
biscuits.cpp:73:7: warning: unused variable 'val' [-Wunused-variable]
73 | int val = a.back();
| ^~~
# |
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 |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
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 |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
304 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 |
312 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
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 |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
308 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
340 KB |
Output is correct |
2 |
Correct |
29 ms |
1236 KB |
Output is correct |
3 |
Correct |
23 ms |
1108 KB |
Output is correct |
4 |
Correct |
23 ms |
1108 KB |
Output is correct |
5 |
Correct |
22 ms |
1108 KB |
Output is correct |
6 |
Correct |
27 ms |
1108 KB |
Output is correct |
7 |
Correct |
27 ms |
1108 KB |
Output is correct |
8 |
Correct |
26 ms |
1108 KB |
Output is correct |
9 |
Correct |
25 ms |
1096 KB |
Output is correct |
10 |
Correct |
18 ms |
1192 KB |
Output is correct |
# |
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 |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
304 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
304 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
312 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
308 KB |
Output is correct |
30 |
Correct |
1 ms |
304 KB |
Output is correct |
31 |
Correct |
1 ms |
308 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
296 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
2 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
300 KB |
Output is correct |
37 |
Correct |
7 ms |
340 KB |
Output is correct |
38 |
Correct |
29 ms |
1236 KB |
Output is correct |
39 |
Correct |
23 ms |
1108 KB |
Output is correct |
40 |
Correct |
23 ms |
1108 KB |
Output is correct |
41 |
Correct |
22 ms |
1108 KB |
Output is correct |
42 |
Correct |
27 ms |
1108 KB |
Output is correct |
43 |
Correct |
27 ms |
1108 KB |
Output is correct |
44 |
Correct |
26 ms |
1108 KB |
Output is correct |
45 |
Correct |
25 ms |
1096 KB |
Output is correct |
46 |
Correct |
18 ms |
1192 KB |
Output is correct |
47 |
Correct |
9 ms |
340 KB |
Output is correct |
48 |
Correct |
26 ms |
1392 KB |
Output is correct |
49 |
Correct |
12 ms |
420 KB |
Output is correct |
50 |
Correct |
18 ms |
1176 KB |
Output is correct |
51 |
Correct |
10 ms |
1236 KB |
Output is correct |
52 |
Correct |
5 ms |
340 KB |
Output is correct |
53 |
Correct |
9 ms |
1108 KB |
Output is correct |
54 |
Correct |
56 ms |
1196 KB |
Output is correct |
55 |
Correct |
54 ms |
1216 KB |
Output is correct |
56 |
Correct |
51 ms |
1224 KB |
Output is correct |
57 |
Correct |
44 ms |
1240 KB |
Output is correct |