#include "biscuits.h"
//#include"grader.cpp"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll INFL = numeric_limits<ll>::max();
vector<ll> ct, v, ub;
ll solve(int id, ll carry, ll x){
if(id == -1)
return 1;
if(ub[id] < carry)
return 1;
ll minus = min(v[id], carry);
carry-=minus;
ll ret = solve(id-1,carry*2,x);
// cerr << id << ' ' << carry << ' ' << x << endl;
// cerr << "->" << carry+x << ' ' << ct[id] << ' ' << minus << endl;
if(carry+x <= ct[id]-minus)
ret += solve(id-1, (max(0ll, x+carry+minus-v[id]))*2, x);
return ret;
}
bool solvetest(int id, ll carry, ll x){
if(id == -1)
return false;
ll minus = min(v[id], carry);
carry-=minus;
ll ret = solve(id-1,carry*2,x);
if(carry+x <= ct[id]-minus)
return true;
return ret;
}
void bsearch(int id, ll x){
ll ini = -1, fim = 1000000000000000000;
// cerr << id << ' ' <<fim << endl;
while(ini!=fim){
// cerr << ini << ' ' << fim << '\n';
ll m = (ini+fim+1)>>1;
if(solvetest(id,m,x))
ini = m;
else fim = m-1;
}
ub[id] = ini;
}
long long count_tastiness(long long x, std::vector<long long> a) {
a.resize(60,0);
ct = v = a;
int k = a.size();
map<ll,ll> dp;
auto getdp =[&](ll vi, ll carry){
return dp.lower_bound(2*(carry-vi))->ss + dp.lower_bound(2*(carry+x-vi))->ss;
};
dp[0] = 1;
dp[INFL] = 0;
auto dc =[&](ll l, ll r, ll respl, ll respr, ll vi, map<ll,ll> & newdp, auto dc) -> void {
if(l > r || respl == respr)
return;
ll m = (l+r)>>1;
newdp[m] = getdp(vi,m);
dc(l,m-1,respl,newdp[m],vi,newdp,dc);
dc(m+1,r,newdp[m],respr,vi,newdp,dc);
};
for(int i = 0; i < 60; i++){
map<ll,ll> newdp;
newdp[0] = getdp(v[i],0);
newdp[INFL] = 0;
dc(1,4e18, newdp[0], 0, v[i], newdp, dc);
dp.swap(newdp);
}
return dp[0];
}
Compilation message
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:58:6: warning: unused variable 'k' [-Wunused-variable]
58 | int k = a.size();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
212 KB |
Output is correct |
3 |
Correct |
5 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
212 KB |
Output is correct |
5 |
Correct |
4 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
212 KB |
Output is correct |
7 |
Correct |
4 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
212 KB |
Output is correct |
9 |
Correct |
5 ms |
212 KB |
Output is correct |
10 |
Correct |
4 ms |
212 KB |
Output is correct |
11 |
Correct |
5 ms |
212 KB |
Output is correct |
12 |
Correct |
4 ms |
212 KB |
Output is correct |
13 |
Correct |
4 ms |
212 KB |
Output is correct |
14 |
Correct |
7 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
212 KB |
Output is correct |
3 |
Correct |
6 ms |
212 KB |
Output is correct |
4 |
Correct |
6 ms |
300 KB |
Output is correct |
5 |
Correct |
6 ms |
312 KB |
Output is correct |
6 |
Correct |
6 ms |
212 KB |
Output is correct |
7 |
Correct |
5 ms |
312 KB |
Output is correct |
8 |
Correct |
6 ms |
300 KB |
Output is correct |
9 |
Correct |
4 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
2764 KB |
Output is correct |
2 |
Correct |
522 ms |
2500 KB |
Output is correct |
3 |
Correct |
830 ms |
2736 KB |
Output is correct |
4 |
Correct |
6 ms |
312 KB |
Output is correct |
5 |
Correct |
7 ms |
212 KB |
Output is correct |
6 |
Correct |
7 ms |
320 KB |
Output is correct |
7 |
Correct |
6 ms |
212 KB |
Output is correct |
8 |
Execution timed out |
1088 ms |
2708 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1078 ms |
52388 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
3 ms |
212 KB |
Output is correct |
3 |
Correct |
5 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
212 KB |
Output is correct |
5 |
Correct |
4 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
212 KB |
Output is correct |
7 |
Correct |
4 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
212 KB |
Output is correct |
9 |
Correct |
5 ms |
212 KB |
Output is correct |
10 |
Correct |
4 ms |
212 KB |
Output is correct |
11 |
Correct |
5 ms |
212 KB |
Output is correct |
12 |
Correct |
4 ms |
212 KB |
Output is correct |
13 |
Correct |
4 ms |
212 KB |
Output is correct |
14 |
Correct |
7 ms |
344 KB |
Output is correct |
15 |
Correct |
3 ms |
212 KB |
Output is correct |
16 |
Correct |
3 ms |
212 KB |
Output is correct |
17 |
Correct |
6 ms |
212 KB |
Output is correct |
18 |
Correct |
6 ms |
300 KB |
Output is correct |
19 |
Correct |
6 ms |
312 KB |
Output is correct |
20 |
Correct |
6 ms |
212 KB |
Output is correct |
21 |
Correct |
5 ms |
312 KB |
Output is correct |
22 |
Correct |
6 ms |
300 KB |
Output is correct |
23 |
Correct |
4 ms |
212 KB |
Output is correct |
24 |
Correct |
236 ms |
2764 KB |
Output is correct |
25 |
Correct |
522 ms |
2500 KB |
Output is correct |
26 |
Correct |
830 ms |
2736 KB |
Output is correct |
27 |
Correct |
6 ms |
312 KB |
Output is correct |
28 |
Correct |
7 ms |
212 KB |
Output is correct |
29 |
Correct |
7 ms |
320 KB |
Output is correct |
30 |
Correct |
6 ms |
212 KB |
Output is correct |
31 |
Execution timed out |
1088 ms |
2708 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |