#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int ans;
long long count_tastiness(long long X, std::vector<long long> vec) {
ans=1;//0
unordered_map<int,__int128> pref;
pref[-1]=1;
while((int)vec.size()<140)vec.push_back(0);
for(int i=0;i<140;i++){ // let's count the numbers st the biggest bit is 2^i
int smallest=i;
__int128 debt=0;
for(int j=i-1;j>=0;j--){ // let's find smallest j such that i can fill everything from [j,i-1]
debt*=2;
debt+=X;
debt-=vec[j];
if(debt<=0)smallest=min(smallest,j);
if(debt>oo)break; // no way to repay
debt=max((__int128)0ll,debt);
}
pref[i]=pref[i-1];
if(smallest == i){
if(vec[i]>=X){
ans+=pref[i-1];
pref[i]+=pref[i-1];
}
continue;
}
__int128 sum = 0;
for(int j=i;j>=smallest;j--){
__int128 t=1ll<<(j-smallest);
sum+=t*(__int128)vec[j];
}
__int128 res=sum/(__int128)X;
res=min(res,(__int128)((1ll<<(i-smallest+1))-1));
res-=(__int128)(1ll<<(i-smallest));
if(res+1<=0)continue;
res++;
res*=pref[smallest-1];
ans+=(int)res;
pref[i]+=res;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
348 KB |
Output is correct |
2 |
Incorrect |
22 ms |
860 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |