#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!
const ll OO = (ll)1e18;
struct Rect { // x = r - l, y = r + l
ll xLo, xHi, yLo, yHi;
bool contains (ll x, ll y) {
return (xLo <= x && x <= xHi && yLo <= y && y <= yHi);
}
void dbg () {
cerr << "rect: " << xLo << " " << xHi << " " << yLo << " " << yHi << "\n";
}
};
Rect merge (const Rect& a, const Rect& b) {
return Rect{max(a.xLo, b.xLo), min(a.xHi, b.xHi), max(a.yLo, b.yLo), min(a.yHi, b.yHi)};
}
bool test (ll UB, int& N, vector<ll>& dist, vector<int>& lenDown, const int& costBridge) {
// cerr << "test: " << UB << "\n";
Rect intersection = Rect{-OO, OO, -OO, OO};
for (int iL = 0; iL < N-1; iL++) {
for (int iR = iL+1; iR < N; iR++) {
ll l = dist[iL], r = dist[iR];
if (r - l + lenDown[iR] + lenDown[iL] > UB) {
ll delta = UB - costBridge - lenDown[iL] - lenDown[iR];
if (delta < 0) {
return false;
}
else {
ll xMid = r - l, yMid = r + l;
intersection = merge(intersection, Rect{xMid - delta, xMid + delta, yMid - delta, yMid + delta});
}
}
}
}
// intersection.dbg();
bool res = false;
for (int iL = 0; iL < N-1; iL++) {
for (int iR = iL+1; iR < N; iR++) {
ll l = dist[iL], r = dist[iR];
ll x = r - l, y = r + l;
if (intersection.contains(x, y)) {
res = true;
}
}
}
return res;
}
ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
vector<ll> dist(N, 0);
for (int i = 0; i < N-1; i++) {
dist[i+1] = dist[i] + lenSide[i];
}
ll loBS = 0, hiBS = OO;
while (loBS < hiBS-1) {
ll midBS = loBS + (hiBS - loBS) / 2;
assert(loBS <= midBS && midBS <= hiBS);
if (test(midBS, N, dist, lenDown, costBridge)) {
hiBS = midBS;
}
else {
loBS = midBS;
}
}
return hiBS;
}
