#include "shortcut.h"
#include <bitsdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e16;
const int maxn=(1e6)+10;
int n,c;
ll s[maxn],d[maxn];
ll m1[3010][3010],m2[3010][3010],m3[3010][3010],m4[3010][3010];
vector<ll> D;
void update(ll &x,ll &y) { if (x<y) x=y; }
ll cmax(ll x,ll y) { if (x>y) return x; return y; }
ll solve(ll M) {
for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) {
if (s[j]-s[i]+d[i]+d[j]>M) {
m1[i][j]=s[i]+s[j]+d[i]+d[j]+c;
m2[i][j]=s[i]-s[j]+d[i]+d[j]+c;
m3[i][j]=-s[i]+s[j]+d[i]+d[j]+c;
m4[i][j]=-s[i]-s[j]+d[i]+d[j]+c;
} else m1[i][j]=m2[i][j]=m3[i][j]=m4[i][j]=-INF;
if (i>1) update(m4[i][j],m4[i-1][j]); if (j>i+1) update(m4[i][j],m4[i][j-1]);
}
for (int len=2;len<=n;len++) for (int l=1,r;l+len-1<=n;l++) {
r=l+len-1;
if (r>l+1) update(m2[l][r],m2[l][r-1]),update(m2[l][r],m2[l+1][r]);
}
for (int len=n;len>=2;len--) for (int l=1,r;l+len-1<=n;l++) {
r=l+len-1;
if (l>1) update(m3[l][r],m3[l-1][r]); if (r<n) update(m3[l][r],m3[l][r+1]);
}
ll res=INF,t;
for (int l=n;l>=1;l--) for (int r=n;r>=l+1;r--) {
if (l+1<r) update(m1[l][r],m1[l+1][r]); if (r<n) update(m1[l][r],m1[l][r+1]);
t=cmax(cmax(m1[l][r]-s[l]-s[r],m2[l][r]-s[l]+s[r]),cmax(m3[l][r]-s[r]+s[l],m4[l][r]+s[l]+s[r]));
if (t<res) res=t;
}
//printf("%lld\n",res);
return max(res,M);
}
ll find_shortcut(int N,vector<int> LLL,vector<int> DDD,int CCC) {
n=N;
for (int i=1;i<=n;i++) {
if (i>1) s[i]=s[i-1]+LLL[i-2];
d[i]=DDD[i-1];
}
c=CCC;
D.push_back(0);
for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++)
D.push_back(s[j]-s[i]+d[i]+d[j]);
sort(D.begin(),D.end());
D.resize(unique(D.begin(),D.end())-D.begin());
//for (ll x : D) printf("%lld ",x); puts("");
int l=0,r=(int)D.size()-1,mid; ll res;
while (l<=r) {
mid=(l+r)>>1;
ll t=solve(D[mid]);
if (mid<(int)D.size()-1&&t>=D[mid+1]) l=mid+1;
else res=t,r=mid-1;
}
//printf("HI %d %lld\n",res,solve(D[res]));
//exit(0);
return res;
}
Compilation message
shortcut.cpp:2:10: fatal error: bitsdc++.h: No such file or directory
2 | #include <bitsdc++.h>
| ^~~~~~~~~~~~
compilation terminated.
