Submission #596383

#TimeUsernameProblemLanguageResultExecution timeMemory
596383kshitij_sodaniUplifting Excursion (BOI22_vault)C++14
0 / 100
222 ms8952 KiB
#include <bits/stdc++.h> using namespace std; typedef long long llo; #define a first #define b second #define pb push_back #define endl '\n' llo n,dd; llo it[350]; llo cc[601]; llo dp[2000001]; deque<pair<llo,llo>> zz[301]; llo ans=-1; void apply(int l,int r){ for(int j=l;j<=r;j++){ llo ax=j*min(it[j],n); llo y=0; llo z=0; llo su3=n*n*n; for(llo ii=0;ii<=su3;ii++){ // llo y=ii%j; if(dp[ii]>=0){ pair<llo,llo> cur={dp[ii]-z,ii}; while(zz[y].size()){ if(zz[y].back().a>=cur.a){ zz[y].pop_back(); } else{ break; } } zz[y].pb(cur); } while(zz[y].size()){ if(zz[y].front().b<ii-ax){ zz[y].pop_front(); } else{ break; } } if(zz[y].size()){ llo xx=zz[y].front().a+z; if(dp[ii]==-1){ dp[ii]=xx; } dp[ii]=min(dp[ii],xx); } y++; if(y==j){ y=0; z++; } } } } llo pp; llo su3=0; void solve(int l,int r){ if(l==r){ llo ac=0; for(int j=r+1;j<=n;j++){ ac+=((it[j]-min(it[j],n)))*j; } if(ac>pp){ return; } llo cur2=pp-ac; int i=l; //cout<<cur2<<",,"<<ac<<","<<pp<<endl; for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){ if(dp[j]>=0){ //if((cur2-j)%i==0){ llo x=(cur2-j)/i; if(x<=it[i]){ llo y=dp[j]+x; y+=ac; if(ans==-1){ ans=y; } ans=min(ans,y); } //} } } } else{ int mid=(l+r)/2; vector<llo> dp2; for(int ii=0;ii<=su3;ii++){ dp2.pb(dp[ii]); } apply(l,mid); solve(mid+1,r); for(int ii=0;ii<=su3;ii++){ dp[ii]=dp2[ii]; } apply(mid+1,r); solve(l,mid); for(int ii=0;ii<=su3;ii++){ dp[ii]=dp2[ii]; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>dd; llo cot=0; llo ma=0; llo acc=0; for(llo i=0;i<n;i++){ llo aa; cin>>aa; cot+=aa; cc[i]=aa; acc+=aa; } llo su=0; for(llo i=0;i<=n;i++){ cin>>it[i]; su+=it[i]*i; cot+=it[i]; cc[n+i]=i; } for(llo i=0;i<=2*n;i++){ ma=max(ma,cc[i]); } su3=n*n*n; if(su<dd){ cout<<"impossible"<<endl; return 0; } llo cur=su-dd; pp=cur; it[0]=0; for(int i=0;i<=su3;i++){ dp[i]=-1; } dp[0]=0; solve(1,n); /*for(llo i=1;i<=n;i++){ llo su2=0; llo ac=0; for(llo j=i+1;j<=n;j++){ llo xx=it[j]-n; if(xx<0){ xx=0; } ac+=xx; su2+=xx*j; } if(su2>cur){ continue; } llo su3=0;//n*n*n; for(llo j=1;j<i;j++){ su3+=j*min(it[j],i); } for(llo j=i+1;j<=n;j++){ su3+=j*min(it[j],n); } for(llo j=0;j<=su3;j++){ dp[j]=-1; } dp[0]=0; su3=0; for(llo j=1;j<=n;j++){ if(j==i){ continue; } if(j<i){ su3+=j*min(it[j],i); } else{ su3+=j*min(it[j],n); } for(llo jj=0;jj<j;jj++){ zz[jj].clear(); } llo ax=j*min(it[j],n); llo y=0; llo z=0; for(llo ii=0;ii<=su3;ii++){ // llo y=ii%j; if(dp[ii]>=0){ pair<llo,llo> cur={dp[ii]-z,ii}; while(zz[y].size()){ if(zz[y].back().a>=cur.a){ zz[y].pop_back(); } else{ break; } } zz[y].pb(cur); } while(zz[y].size()){ if(zz[y].front().b<ii-ax){ zz[y].pop_front(); } else{ break; } } if(zz[y].size()){ llo xx=zz[y].front().a+z; if(dp[ii]==-1){ dp[ii]=xx; } dp[ii]=min(dp[ii],xx); } y++; if(y==j){ y=0; z++; } } } llo cur2=cur-su2; for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){ if(dp[j]>=0){ //if((cur2-j)%i==0){ llo x=(cur2-j)/i; if(x<=it[i]){ llo y=dp[j]+x; y+=ac; if(ans==-1){ ans=y; } ans=min(ans,y); } //} } } }*/ if(ans==-1){ cout<<"impossible"<<endl; } else{ //cout<<ans<<endl; cout<<cot-ans<<endl; } //else find minimum number of elements with sum su-dd return 0; }
#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...
#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...