제출 #1052538

#제출 시각아이디문제언어결과실행 시간메모리
1052538noyancanturkPacking Biscuits (IOI20_biscuits)C++17
100 / 100
7 ms1472 KiB
#include "biscuits.h" #include <bits/stdc++.h> using namespace std; using lint=long long; using llint=__int128_t; llint inf=1e20; lint count_tastiness(lint X,vector<lint> a) { llint x=X; int n=a.size(); llint b[200]{}; for(int i=0;i<200;i++){ if(i<n)b[i]+=a[i]; if(x<b[i]){ b[i+1]=(b[i]-x)/2; b[i]=x+((b[i]-x)&1); } //cerr<<lint(b[i])<<" "; }//cerr<<"\n"; llint dp[200]{}; llint dppref[200]{}; for(int i=0;i<200;i++){ if(inf<(x<<i))break; if(x<=b[i]){ if(i)dp[i]=dppref[i-1]; else dp[i]=1; }else{ dp[i]=0; llint neednow=x; for(int j=i;0<=j;j--){ neednow-=b[j]; if(neednow<=0){ neednow=x+neednow; if(neednow<=0){ dp[i]+=dppref[j]; break; }else if(j)dp[i]+=dppref[j-1]; else dp[i]++; } neednow*=2; if(inf<neednow)break; } } dppref[i]=dp[i]; if(i)dppref[i]+=dppref[i-1]; else dppref[i]++; } llint ans=1; for(int i=0;i<200;i++){ ans+=dp[i]; //if(i<5)cerr<<lint(dp[i])<<" "<<lint(dppref[i])<<" "<<i<<" dpval\n"; } return ans; }
#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...