Submission #1069919

#TimeUsernameProblemLanguageResultExecution timeMemory
1069919jerzyk비스킷 담기 (IOI20_biscuits)C++17
100 / 100
21 ms7548 KiB
#include <bits/stdc++.h> #include "biscuits.h" using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; const int H = 60; const ll N = (1LL<<(ll)H); const int II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int NN = 1000 * 1000 + 7; ll drz[NN], il[NN]; int l[NN], r[NN]; int cnt; ll answer = 0LL; void Init() { for(int i = 1; i <= 4000; ++i) { drz[i] = 0LL; l[i] = 0; r[i] = 0; } for(int i = 1; i <= H; ++i) {l[i] = i + 1; drz[i] = 1LL;} drz[H + 1] = 1LL; cnt = H + 1; } void Copy(int v1, int v2, ll a, ll b, ll lim) { if((a + b) / 2LL <= lim) l[v2] = l[v1]; if((a + b) / 2LL > lim) { if(l[v1] != 0) { ++cnt; l[v2] = cnt; Copy(l[v1], l[v2], a, (a + b) / 2LL, lim); } } if((a + b) / 2LL < lim) { if(r[v1] != 0) { ++cnt; r[v2] = cnt; Copy(r[v1], r[v2], (a + b) / 2LL + 1LL, b, lim); } } //cerr << v2 << " Copy " << l[v2] << " " << r[v2] << "\n"; drz[v2] = drz[l[v2]] + drz[r[v2]]; } void Upd(ll b, ll lim) { int v1; ll ran = (N - 1LL) / 2LL; v1 = 1; while(ran + 1LL > b) { ran /= 2LL; v1 = l[v1]; } //cerr << b << " " << "Upd: " << v1 << " " << ran << " " << lim << "\n"; if(lim >= b - 1LL) { r[v1] = l[v1]; }else { ++cnt; r[v1] = cnt; //cerr << "cp " << l[v1] << " " << r[v1] << "\n"; Copy(l[v1], r[v1], 0, ran, lim); } while(v1 > 0) { drz[v1] = drz[l[v1]] + drz[r[v1]]; --v1; } } long long count_tastiness(long long x, vector<long long> _a) { Init(); int n = _a.size() - 1; for(int i = 0; i <= n; ++i) il[i] = _a[i]; if(il[0] >= x) Upd(1LL, 0LL); //cerr << "DP: \n"; for(int i = 1; i <= 60; ++i) { if(x * (1LL<<(ll)i) > (ll)I) break; il[i] *= (1LL<<(ll)i); ll ned = max(0LL, (x * (1LL<<(ll)i) - il[i])); ll lim = (il[i - 1] - ned) / x; if(il[i - 1] - ned < 0LL) lim = -1LL; lim = min(lim, (1LL<<(ll)(i)) - 1LL); //cerr << i << " " << "bis: " << ned << " " << lim << "\n"; if(lim >= 0LL) Upd((1LL<<(ll)i), lim); il[i] += il[i - 1]; //cerr << drz[1] << "\n"; } for(int i = 0; i <= 100; ++i) il[i] = 0LL; return drz[1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...