제출 #371325

#제출 시각아이디문제언어결과실행 시간메모리
371325pit4h비스킷 담기 (IOI20_biscuits)C++14
0 / 100
2 ms364 KiB
#include "biscuits.h" #include<bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; const ll INF = 2e18+1; ll count_tastiness(ll x, vector<ll> a) { int k = a.size(); vector<ll> dp(k), dp0(k), pref(k); pref[0] = a[0]; for(int i=1; i<k; ++i) { pref[i] = pref[i-1]/2 + a[i]; } for(int i=0; i<k; ++i) { if(i>0) { dp0[i] = dp[i-1]; } else { dp0[i] = 1; } ll sum = 0; dp[i] = 1; for(int j=i; j>=0; --j) { if(pref[j] - (ll)sum >= x) { dp[i] += dp0[j]; if(sum < INF/2 && sum + x < INF/2) { sum += x; sum = max(0LL, sum - a[j]); sum *= 2; } else { sum = INF; } } else { sum = max(0LL, sum - a[j]); if(sum < INF/2) sum *= 2; else sum = INF; } } } if(dp[k-1] < 0LL) { assert(false); } return dp[k-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...