Submission #1191919

#TimeUsernameProblemLanguageResultExecution timeMemory
1191919simona1230Shortcut (IOI16_shortcut)C++20
0 / 100
0 ms324 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; long long fl[200001],fr[200001]; long long p[200001]; long long h1[3001][3001],h2[3001][3001]; long long ans1[200001],ans2[200001]; long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { l.push_back(0); fl[0]=d[0]; ans1[0]=d[0]; for(long long i=1;i<n;i++) { fl[i]=max(l[i-1]+fl[i-1],(long long)d[i]); ans1[i]=max(ans1[i-1],fl[i-1]+l[i-1]+d[i]); } fr[n-1]=d[n-1]; ans2[n-1]=d[n-1]; for(long long i=n-2;i>=0;i--) { fr[i]=max(l[i]+fr[i+1],(long long)d[i]); //cout<<i<<"- "<<fr[i]<<endl; ans2[i]=max(ans2[i+1],fr[i+1]+l[i]+d[i]); } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { h1[i][j]=max(h1[i][j-1],p[j]-l[j]-p[i]+l[i]+d[j]); } } for(int i=0;i<n;i++) { h2[i][i]=d[i]; for(int j=i-1;j>=0;j--) { h2[i][j]=max(h2[i][j+1],p[i]-l[i]-p[j]+l[j]+d[j]); } } p[0]=l[0]; for(long long i=1;i<l.size();i++) p[i]=p[i-1]+l[i]; long long ans=1e18; for(long long i=0;i<n;i++) { //cout<<i<<": "<<ans1[i]<<" "<<ans2[i]<<endl; for(long long j=i;j<n;j++) { long long x=d[i],y=d[j]; long long all=p[j]-l[j]-p[i]+l[i]; long long curr=fl[i]+fr[j]+min((long long)c,all); for(long long z=i;z<=j;z++) { long long d1=p[z]-l[z]-p[i]+l[i]; long long d2=all-d1+c; x=max(x,min(d1,d2)+d[z]); d1=p[j]-l[j]-p[z]+l[z]; d2=all-d1+c; y=max(y,min(d1,d2)+d[z]); } if(i)curr=max(curr,fl[i-1]+l[i-1]+x); if(j!=n-1)curr=max(curr,fr[j+1]+l[j]+y); int z2=i; for(long long z1=i;z1<=j;z1++) { while(1) { if(z2==j+1)break; long long d1=p[z2]-l[z2]-p[z1]+l[z1]; long long d2=all-d1+c; if(d1<d2)z2++; else break; } //cout<<i<<" "<<j<<" "<<z1<<" "<<z2<<endl; if(z2<=j) { //cout<<d[z1]+p[z1]-l[z1]-p[i]+l[i]+c+h2[j][z2]<<endl; curr=max(curr,d[z1]+p[z1]-l[z1]-p[i]+l[i]+c+h2[j][z2]); } //cout<<d[z1]+h1[i][z2-1]<<endl; curr=max(curr,d[z1]+h1[i][z2-1]); } curr=max(curr,ans1[i]); curr=max(curr,ans2[j]); //cout<<i<<" "<<j<<" "<<curr<<" "<<fl[i]<<" "<<fr[j]<<" "<<x<<" "<<y<<endl; ans=min(ans,curr); } } return ans; }

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...