#include "shortcut.h"
using namespace std;
#include <vector>
#include <iostream>
long long inf=1e17;
long long spar[6005];
long long atarna[6005];
long long pref[6005];
long long suff[6005];
long long dp[6005][6005];
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[10005];
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=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;
}
