제출 #1069822

#제출 시각아이디문제언어결과실행 시간메모리
1069822jerzyk비스킷 담기 (IOI20_biscuits)C++17
0 / 100
1119 ms885772 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 II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int N = 1000 * 1000 + 7; ll il[N]; vector<pair<ll, ll>> zbi; ll answer = 0LL; void Upd(ll b, ll lim) { vector<pair<ll, ll>> nxt; for(int i = 0; i < (int)zbi.size() && (zbi[i].st <= lim); ++i) { pair<ll, ll> nw = make_pair(b + zbi[i].st, b + min(lim, zbi[i].nd)); answer += nw.nd - nw.st + 1LL; nxt.pb(nw); } if((int)nxt.size() > 0) { int i = (int)zbi.size() - 1; if(zbi[i].nd + 1LL == nxt[0].st) { nxt[0].st = zbi[i].st; zbi.pop_back(); } } for(int i = 0; i < (int)nxt.size(); ++i) zbi.pb(nxt[i]); } long long count_tastiness(long long x, std::vector<long long> _a) { zbi.clear(); answer = 0LL; int n = _a.size() - 1; for(int i = 0; i <= n; ++i) il[i] = _a[i]; if(il[0] >= x) { answer += 2LL; zbi.pb(make_pair(0LL, 1LL)); } else { answer += 1LL; zbi.pb(make_pair(0LL, 0LL)); } //cerr << "DP: \n"; for(int i = 1; i <= 60; ++i) { if(x * (1LL<<(ll)i) > I) break; il[i] *= (1LL<<(ll)i); ll ned = max(0LL, (x * (1LL<<(ll)i) - il[i])); ll lim = (il[i - 1] - ned) / x; 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]; } for(int i = 0; i <= 100; ++i) il[i] = 0LL; return answer; }
#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...