#include "shortcut.h" using namespace std; #include <vector> #include <iostream> long long inf=1e17; long long spar[100005]; long long atarna[100005]; long long pref[100005]; long long suff[100005]; 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); } vector<int>vec; long long evalciclu(int m1,int m2,int c) { long long maxim=0; for(int i=0;i<vec.size();i++) { for(int j=i+1;j<vec.size();j++) { maxim=max(maxim,dist(vec[i],vec[j],m1,m2,c)+atarna[vec[i]]+atarna[vec[j]]); } } return maxim; } pair<long long,long long>eval(int i,int j,int c) { vec.clear(); 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++) { //vec.push_back(spar[c1]-spar[c1-1]); vec.push_back(c1); } //vec.push_back(c); long long rezciclu=evalciclu(i,j,c); 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=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=1; 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
      |         ^~~~