Submission #1022238

#TimeUsernameProblemLanguageResultExecution timeMemory
1022238amirhoseinfar1385Shortcut (IOI16_shortcut)C++17
0 / 100
18 ms456 KiB
#include "shortcut.h" #include<bits/stdc++.h> using namespace std; const long long maxn=1000000+10; long long inf=1e16,n,c; long long alld[maxn],mainres=inf,mxa[maxn],mxb[maxn]; vector<long long>all; long long pors(long long l,long long r){ long long b=all[r]-all[l]+c; long long fake=0; for(long long i=0;i<n;i++){ if(i<=l){ fake=max(fake,alld[i]+all[l]-all[i]+min(c,b-c)+mxb[r]); fake=max(fake,alld[i]+all[i]-(i==0?0:all[i-1])+(i==0?0:mxa[i-1])); }else if(i>=r){ fake=max(fake,alld[i]+all[i]-all[r]+min(c,b-c)+mxa[l]); fake=max(fake,alld[i]-all[i]+all[i+1]+mxb[i+1]); }else{ fake=max(fake,min(all[i]-all[l],b-(all[i]-all[l]))+mxa[l]+alld[i]); fake=max(fake,min(all[r]-all[i],b-(all[r]-all[i]))+mxb[r]+alld[i]); } } for(long long i=l;i<=r;i++){ int h=lower_bound(all.begin(),all.end(),all[i]+b/2)-all.begin(); for(int j=h-10;j<=h+10;j++){ if(j>r||j<l||j==i){ continue; } fake=max(fake,min(b-abs(all[j]-all[i]),abs(all[j]-all[i]))+alld[i]+alld[j]); } h=lower_bound(all.begin(),all.end(),all[i]-b/2)-all.begin(); for(int j=h-10;j<=h+10;j++){ if(j>r||j<l||j==i){ continue; } fake=max(fake,min(b-abs(all[j]-all[i]),abs(all[j]-all[i]))+alld[i]+alld[j]); } } return fake; } void solve(long long l,long long r,long long tl=0,long long tr=n-1){ for(long long i=0;i<n;i++){ for(long long j=i;j<n;j++){ mainres=min(mainres,pors(i,j)); } } } long long find_shortcut(int n_, std::vector<int> l, std::vector<int> d, int c_) { n=n_; c=c_; all.push_back(0); alld[0]=d[0]; l.push_back(0); for(long long i=1;i<n;i++){ all.push_back(all.back()+l[i-1]); alld[i]=d[i]; } for(long long i=0;i<n;i++){ if(i!=0){ mxa[i]=max(mxa[i-1]+l[i-1],alld[i]); }else{ mxa[i]=alld[i]; } } all[n]=all[n-1]; for(long long i=n-1;i>=0;i--){ mxb[i]=max(mxb[i+1]+l[i],alld[i]); } solve(0,n-1); return mainres; }
#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...