Submission #1233171

#TimeUsernameProblemLanguageResultExecution timeMemory
1233171Saul0906Shortcut (IOI16_shortcut)C++20
0 / 100
0 ms324 KiB
#include "shortcut.h" #include <bits/stdc++.h> #define all(a) a.begin(), a.end() #define rep(a,b,c) for(int a=b; a<c; a++) #define repr(a,b,c) for(int a=b-1; a>c-1; a--) #define repa(a,b) for(auto a:b) #define ll long long #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define pii pair<int, int> #define fi first #define se second #define mid ((l+r)>>1) using namespace std; using vi = vector<int>; const ll inf=1e18; const int N=2e5+5; ll dis[N], rdis[N], sp[20][N], rsp[20][N]; ll query(int l, int r, bool z){ if(l>r) return 0; ll k=__lg(r-l+1), x=1<<k; if(z) return max(rsp[k][l],rsp[k][r-x+1]); else return max(sp[k][l],sp[k][r-x+1]); } long long find_shortcut(int n, vector<int> l, vector<int> d, int c){ ll dp[n+5][n+5]{}; dis[0]=rdis[n-1]=0; repr(i,n-1,0) rdis[i]=rdis[i+1]+l[i]; rep(i,1,n) dis[i]=dis[i-1]+l[i-1]; rep(i,0,n){ sp[0][i]=dis[i]+d[i]; rsp[0][i]=rdis[i]+d[i]; } rep(j,1,20){ rep(i,0,n){ if(i+(1<<j)>n) continue; sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<j-1)]); rsp[j][i]=max(rsp[j-1][i],rsp[j-1][i+(1<<j-1)]); } } rep(i,0,n) rep(j,i+1,n) dp[i][j]=max(dp[i][j],dis[j]-dis[i]+d[i]+d[j]); rep(i,0,n) rep(j,i,n){ dp[i][j+1]=max(dp[i][j+1],dp[i][j]); dp[i+1][j]=max(dp[i+1][j],dp[i][j]); } ll ans=inf; rep(i,0,n){ rep(j,i+1,n){ ll v=0, ind=i; rep(k,i,j+1){ while(ind<=j && dis[ind]-dis[k]<=dis[k]-dis[i]+dis[j]-dis[ind]+c) ind++; v=max(v,d[k]+query(k+1,ind-1,0)-dis[k]); v=max(v,d[k]+query(ind,j,1)+c+dis[k]-dis[i]-rdis[j]); } int l=i, r=j; while(l<=r){ if(dis[mid]-dis[i]<=dis[r]-dis[mid]+c) l=mid+1; else r=mid-1; } v=max(v,query(0,i,1)+query(i,r,0)-dis[i]-rdis[i]); v=max(v,query(0,i,1)+query(l,j,1)+c-rdis[i]-rdis[j]); l=i, r=j; while(l<=r){ if(dis[j]-dis[mid]<=dis[mid]-dis[i]+c) r=mid-1; else l=mid+1; } v=max(v,query(j,n-1,0)+query(l,j,1)-dis[j]-rdis[j]); v=max(v,query(j,n-1,0)+query(i,r,0)+c-dis[i]-dis[j]); ans=min(ans,v); } } 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...