#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> edge;
const int MAXN = 3010; //2*(max N) actually.
const ll INF = 0x3f3f3f3f3f3f3f3f;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
template<class T>
void setmin (T &a, T b) {
if (b < a) {
a = b;
}
}
template<class T>
void setmax (T &a, T b) {
if (a < b) {
a = b;
}
}
int N;
ll C;
ll L[MAXN]; //length from (i-1) to i
ll PL[MAXN];
ll D[MAXN]; //distance to secondary station (i + N)
bool moo (ll dia) {
//is diameter <= dia?
ll xmymn = LLONG_MIN, xmymx = LLONG_MAX;
ll xpymn = LLONG_MIN, xpymx = LLONG_MAX;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (D[i] + (L[j] - L[i]) + D[j] > dia) {
ll lim = dia - D[i] - D[j] - C;
if (lim < 0) {
return false;
}
//L[i] - L[j] - lim <= x - y <= L[i] - L[j] + lim
//L[i] + L[j] - lim <= x + y <= L[i] + L[j] + lim
setmax(xmymn, L[i] - L[j] - lim);
setmin(xmymx, L[i] - L[j] + lim);
setmax(xpymn, L[i] + L[j] - lim);
setmin(xpymx, L[i] + L[j] + lim);
}
//otherwise everything works
}
}
//debug("x - y: min = %lld, max = %lld.\nx + y: min = %lld, max = %lld.\n", xmymn, xmymx, xpymn, xpymx);
//ok now check if anything is in there
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (xmymn <= L[i] - L[j] && L[i] - L[j] <= xmymx) {
if (xpymn <= L[i] + L[j] && L[i] + L[j] <= xpymx) {
return true;
}
}
}
}
return false;
}
ll find_shortcut (int nnn, vector<int> lll, vector<int> ddd, int ccc) {
//very very preliminary stuff - should also init other stuff
N = nnn;
C = ccc;
for (int i = 1; i < N; i++) {
L[i] = L[i - 1] + lll[i - 1];
}
for (int i = 0; i < N; i++) {
D[i] = ddd[i];
}
ll lo = 0, hi = 1ll << 43;
while (hi - lo > 1) {
ll mid = (lo + hi) >> 1;
if (moo(mid)) {
hi = mid;
} else {
lo = mid;
}
}
return hi;
}
