Submission #802052

#TimeUsernameProblemLanguageResultExecution timeMemory
802052WarinchaiRice Hub (IOI11_ricehub)C++14
0 / 100
247 ms1064 KiB
#include "ricehub.h" #include<bits/stdc++.h> using namespace std; long long sumf[100005]; long long sumb[100005]; long long n; int am; vector<long long>v; long long cost; pair<int,long long> tl(int i,int r,long long mx,long long left){ int en=r; int st=0; int ans=r+1; //cout<<"mx:"<<mx<<endl; while(st<=en){ int m=(st+en)/2; //cout<<"m:"<<m<<" "<<v[i]-v[m]<<" "<<sumb[m]-sumb[r+1]<<"-"<<(r-m+1)<<"*"<<n<<"-"<<v[r+1]<<endl; if(v[i]-v[m]<=mx&&(sumb[m]-sumb[r+1])-(r-m+1)*(n-v[r+1])<=left){ ans=m; en=m-1; }else{ st=m+1; } } //cout<<"r:"<<r<<endl; //cout<<ans<<":"<<left<<"-"<<"("<<sumb[ans]-sumb[r+1]<<"-"<<r+1-ans<<"*"<<n-v[r+1]<<")"<<endl; return {ans,left-((sumb[ans]-sumb[r+1])-(r+1-ans)*(n-v[r+1]))}; } pair<int,long long> tr(int i,int l,long long mx,long long left){ int en=am-1; int st=l; int ans=l-1; while(st<=en){ int m=(st+en)/2; //cout<<"m:"<<m<<endl; //cout<<(sumf[m]-sumf[l-1])-(m-l+1)*(v[l-1])<<endl; if(v[m]-v[i]<=mx&&(sumf[m]-sumf[l-1])-(m-l+1)*(v[l-1])<=left){ ans=m; st=m+1; }else{ en=m-1; } } return {ans,left-((sumf[ans]-sumf[l-1])-(ans-l+1)*(v[l-1]))}; } int cnl=0,cnr=0; int fr(int i){ //cout<<"I:"<<i<<endl; long long left=cost; //cout<<"left:"<<cost<<endl; int l=i+1,r=i-1; bool cl; if(i==0){ cl=1; }else if(i==am-1){ cl=0; }else{ cl=v[i]-v[i-1]<v[i+1]-v[i]; } cnl=0,cnr=0; //cout<<"right, left:"<<r<<" "<<l<<endl; while(left>=0){ if(cl){ //cout<<"going left"<<endl; long long mx; if(l<am){ mx=v[l]-v[i]; }else{ mx=LLONG_MAX; } pair<int,int> move=tl(i,r,mx,left); left=move.second; // if(r==move.first-1){ cnl=1; } r=move.first-1; //cout<<r<<" "<<left<<endl; }else{ //cout<<"going right"<<endl; long long mx; if(r>=0){ mx=v[i]-v[r]; }else{ mx=LLONG_MAX; } pair<int,int> move=tr(i,l,mx,left); left=move.second; if(l==move.first+1){ cnr=1; } l=move.first+1; //cout<<l<<" "<<left<<endl; } //cout<<"result:"<<r<<" "<<l<<endl; if(cnl&&cnr){ break; } cl^=1; } //cout<<"final result:"<<r<<" "<<l<<endl; //cout<<endl; return l-r-1; } int besthub(int r, int l, int x[], long long b) { long long sum=0; cost=b; n=l; am=r; for(int i=0;i<r;i++){ sum+=x[i]; sumf[i]=sum; v.push_back(x[i]); } sum=0; for(int i=r-1;i>=0;i--){ sum+=l-x[i]; sumb[i]=sum; } /*cout<<"info:"<<endl; for(int i=0;i<r;i++){ cout<<sumb[i]<<" "; } cout<<endl;*/ int ans=0; for(int i=0;i<r;i++){ ans=max(ans,fr(i)); } 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...