제출 #596387

#제출 시각아이디문제언어결과실행 시간메모리
596387kshitij_sodaniUplifting Excursion (BOI22_vault)C++14
0 / 100
1 ms852 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=0; void apply(int l,int r){ for(int j=l;j<=r;j++){ llo ax=j*min(it[j],n); su3+=ax; llo y=0; llo z=0; //llo su3=n*n*n; for(int i=0;i<j;i++){ zz[i].clear(); } 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++; } } } } 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){ if(l==r){ llo ac=0; llo ac2=0; for(int j=r+1;j<=n;j++){ ac+=((it[j]-min(it[j],n)))*j; ac2+=(it[j]-min(it[j],n)); } 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+=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); llo su4=su3; solve(mid+1,r); remove(l,mid); for(int ii=0;ii<dp2.size();ii++){ dp[ii]=dp2[ii]; } for(int ii=su3+1;ii<=su4;ii++){ dp[ii]=-1; } apply(mid+1,r); su4=su3; solve(l,mid); remove(l,mid); for(int ii=0;ii<dp2.size();ii++){ dp[ii]=dp2[ii]; } for(int ii=su3+1;ii<=su4;ii++){ dp[ii]=-1; } } } 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=0; if(su<dd){ cout<<"impossible"<<endl; return 0; } llo cur=su-dd; pp=cur; it[0]=0; for(int i=0;i<=n*n*n;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; }

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

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