#include "shortcut.h" using namespace std; #include <vector> #include <iostream> long long inf=1e17; long long spar[3005]; long long atarna[3005]; long long pref[3005]; long long suff[3005]; long long dp[3005][3005]; int n; long long dist(int a,int b,int c,int d,int add) { long long minim=inf; minim=min(minim,spar[b]-spar[a]); minim=min(minim,abs(spar[b]-spar[d])+abs(spar[a]-spar[c])+add); return minim; } pair<long long,int>evalcamij(int pos,int tres,int x,int y,int c) { long long maxim=-inf,dir=-1,max2=-inf; for(int i=pos+1; i<=tres; i++) { maxim=max(maxim,dist(pos,i,x,y,c)+atarna[i]); } for(int i=tres+1; i<=n; i++) { long long calc=dist(pos,i,x,y,c)+atarna[i]; if(calc>maxim) { dir=1; maxim=calc; } } for(int i=1; i<=pos; i++) { max2=max(max2,dist(i,pos,x,y,c)+atarna[i]); } return make_pair(max2+maxim,dir); } long long diff[3005]; long long evalciclu(int cate,long long ciclelenght,int from) { long long maxim=0; for(int i=0; i<cate; i++) { diff[i+cate]=diff[i]+ciclelenght; } int st=0,dr=0; while(st<cate) { while(diff[dr+1]-diff[st]<=ciclelenght/2) { dr++; } if(dr!=st) { if(dr>=cate) { maxim=max(maxim,dp[from+st+1][from+cate-1]+atarna[st+from]-spar[st+from]); maxim=max(maxim,dp[from][from+dr-cate]+ciclelenght+atarna[st+from]-spar[st+from]); } else { maxim=max(maxim,dp[from+st+1][from+dr]+atarna[st+from]-spar[st+from]); } } st++; } return maxim; } pair<long long,long long>eval(int i,int j,int c) { long long worst=0,dir=1; if(c>spar[j]-spar[i]) { return {inf,1}; } worst=pref[i]; if(suff[j]>=worst) { worst=suff[j]; dir=1; } long long ciclelenght=spar[j]-spar[i]+c; for(int c1=i; c1<=j; c1++) { diff[c1-i]=(spar[c1]-spar[i]); } long long rezciclu=evalciclu(j-i+1,ciclelenght,i); if(rezciclu>worst) { worst=rezciclu; dir=-1; } pair<long long,int> ev1=evalcamij(i,j,i,j,c); if(ev1.first>=worst) { worst=ev1.first; dir=ev1.second; } ev1=evalcamij(j,j,i,j,c); if(ev1.first>=worst) { worst=ev1.first; dir=1; } return make_pair(worst,dir); } long long find_shortcut(int m, std::vector<int> l, std::vector<int> d, int c) { n=m; for(int i=2; i<=n; i++) { spar[i]=spar[i-1]+l[i-2]; } for(int i=0; i<n; i++) { atarna[i+1]=d[i]; } long long best=0; for(int z=1; z<=n; z++) { for(int z2=z+1; z2<=n; z2++) { best=max(best,spar[z2]-spar[z]+d[z-1]+d[z2-1]); } } for(int i=1; i<=n; i++) { pref[i]=pref[i-1]; for(int j=1; j<i; j++) { pref[i]=max(pref[i],spar[i]-spar[j]+atarna[i]+atarna[j]); } } for(int i=0;i<=n+1;i++) { for(int j=0;j<=n+1;j++) { dp[i][j]=-inf; } } for(int i=1; i<=n; i++) { dp[i][i]=spar[i]+atarna[i]; for(int j=i+1; j<=n; j++) { dp[i][j]=max(dp[i][j-1],spar[j]+atarna[j]); } } for(int i=n; i>=1; i--) { suff[i]=suff[i+1]; for(int j=n; j>i; j--) { suff[i]=max(suff[i],spar[j]-spar[i]+atarna[i]+atarna[j]); } } for(int i=2; i<=n; i++) { int st=i+1,dr=n; while(st<=dr) { int mij=(st+dr)/2; pair<long long,long long>rez=eval(i,mij,c); if(rez.second==1) { st=mij+1; } else { dr=mij-1; } best=min(best,rez.first); } } return best; }

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
      |         ^~~~