제출 #596477

#제출 시각아이디문제언어결과실행 시간메모리
596477kshitij_sodaniUplifting Excursion (BOI22_vault)C++14
10 / 100
5096 ms157864 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; llo su3=2e6; llo su5=0; void apply(int l,int r){ for(int j=l;j<=r;j++){ if(j==n){ continue; } if(j<n){ } llo ax=(j-n)*min(cc[j],n); //su3=max(su3,su3+ax); //su5=min(su5,su3+ax); //llo su3=n*n*n; for(int i=0;i<abs(j-n);i++){ zz[i].clear(); } if(j<n){ continue; for(llo ii=su3;ii>=su5;ii--){ llo y=ii%abs(j-n); llo z=ii/abs(j-n); 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+abs(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++; }*/ } } else{ //llo y=0; //llo z=0; for(llo ii=su5;ii<=su3;ii++){ llo y=ii%abs(j-n); llo z=ii/abs(j-n); 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); } } } } } void remove(int l,int r){ /*for(int j=l;j<=r;j++){ llo ax=j*min(it[j],n); su3-=ax; }*/ } llo pp; void solve(int l,int r){ //cout<<l<<','<<r<<endl; if(l==r){ if(l==0){ return; } llo ac=0; llo ac2=0; if(l>0){ for(int j=r+1;j<=2*n;j++){ ac+=((cc[j]-min(cc[j],n)))*(j-n); ac2+=(cc[j]-min(cc[j],n)); } for(int j=0;j<n;j++){ ac+=((cc[j]-min(cc[j],n)))*(j-n); ac2+=(cc[j]-min(cc[j],n)); } } else{ return; for(int j=0;j<l;j++){ ac+=((cc[j]-min(cc[j],n)))*(j-n); ac2+=(cc[j]-min(cc[j],n)); } for(int j=n+1;j<=2*n;j++){ ac+=((cc[j]-min(cc[j],n)))*(j-n); ac2+=(cc[j]-min(cc[j],n)); } } /*if(ac>pp){ return; }*/ llo cur2=pp-ac; int i=l; /* if(r==4){ cout<<ac<<":"<<pp<<endl; }*/ //cout<<i<<"::"<<l<<endl; //cout<<cur2<<",,"<<ac<<","<<pp<<endl; //cout<<dp[n*n*n]<<","<<endl; for(llo j=su5;j<=su3;j++){ if(i==n){ continue; } // for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){ if(dp[j]>=0){ /*if(r==4){ cout<<(j-n*n*n)<<"::"<<endl; }*/ /*if(r==6){ cout<<(j-n*n*n)<<","<<endl; }*/ //if(l-n==1){ //cout<<(j-n*n*n)<<":::"<<endl; //} int ok=1; if(i<n){ ok=-1; } if(abs(cur2-j)%abs(i-n)==0){ llo x=abs(cur2-j)/abs(i-n); x*=ok; if(cur2-j<0){ x=-x; } if(x<=cc[i] and x>=0){ llo y=dp[j]+x; y+=ac2; if(ans==-1){ ans=y; } // cout<<(j-n*n*n)<<":"<<r<<":"<<pp<<":"<<cur2<<",,"<<x<<endl; //cout<<cur2-j<<",,,"<<(i-n)<<",,"<<cc[4]<<endl; ans=min(ans,y); } } } } /*ac=0; ac2=0; for(int j=0;j<l;j++){ ac+=((cc[j]-min(cc[j],n)))*(j-n); ac2+=(cc[j]-min(cc[j],n)); } cur2=pp-ac; for(llo j=su5;j<=su3;j++){ if(i==n){ continue; } // for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){ if(dp[j]>=0){ //if(l-n==1){ //cout<<(j-n*n*n)<<":::"<<endl; //} int ok=1; if(i<n){ ok=-1; } if(abs(cur2-j)%abs(i-n)==0){ llo x=(cur2-j)/abs(i-n); x*=ok; if(cur2-j<0){ x=-x; } if(x<=cc[i] and x>=0){ llo y=dp[j]+x; y+=ac2; 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); //remove(l,mid); for(int ii=0;ii<dp2.size();ii++){ dp[ii]=dp2[ii]; } apply(mid+1,r); solve(l,mid); //remove(mid+1,r); for(int ii=0;ii<dp2.size();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; llo su=0; for(llo i=0;i<n;i++){ llo aa; cin>>aa; su+=aa*(i-n); cot+=aa; cc[i]=aa; acc+=aa; } for(llo i=0;i<=n;i++){ cin>>it[i]; su+=it[i]*i; cot+=it[i]; cc[n+i]=it[i]; } for(llo i=0;i<=2*n;i++){ ma=max(ma,cc[i]); } for(int i=1;i<=n;i++){ } //cout<<cc[4]<<":"<<endl; //su3=0; /* if(su<dd){ cout<<"impossible"<<endl; return 0; }*/ llo cur=su-dd; pp=cur; pp+=n*n*n; it[0]=0; for(int i=0;i<=2e6;i++){ dp[i]=-1; } dp[(n*n*n)]=0; solve(0,2*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; }

컴파일 시 표준 에러 (stderr) 메시지

vault.cpp: In function 'void solve(int, int)':
vault.cpp:253:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |   for(int ii=0;ii<dp2.size();ii++){
      |                ~~^~~~~~~~~~~
vault.cpp:260:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |   for(int ii=0;ii<dp2.size();ii++){
      |                ~~^~~~~~~~~~~
#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...