| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 829101 | definitelynotmee | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
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"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];
}