#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!
const ll OO = (ll)1e18;
struct rotateRect {
// X = R+L
// Y = R-L
ll minX, maxX;
ll minY, maxY;
rotateRect (ll a, ll b, ll c, ll d) {minX=a,maxX=b,minY=c,maxY=d;}
void dbg () {
cerr << minX << " " << maxX << ", " << minY << " " << maxY << "\n";
}
bool inside (int x, int y) {
return (minX <= x && x <= maxX && minY <= y && y <= maxY);
}
};
rotateRect intersection (rotateRect& a, rotateRect& b) {
return rotateRect(max(a.minX, b.minX), min(a.maxX, b.maxX), max(a.minY, b.minY), min(a.maxY, b.maxY));
}
bool test (ll ubDist, const int& N, const vector<int>& lenSide, const vector<int>& lenDown, const int& costBridge) {
vector<ll> distFrom0(N, 0);
for (int i = 0; i < N-1; i++) {
distFrom0[i+1] = distFrom0[i] + lenSide[i];
}
rotateRect finalIntersect = rotateRect(-OO, OO, -OO, OO);
for (int l = 0; l < N-1; l++) {
for (int r = l+1; r < N; r++) {
ll distLR = distFrom0[r] - distFrom0[l];
if (distLR + lenDown[l] + lenDown[r] > ubDist) {
ll delta = ubDist - costBridge - lenDown[l] - lenDown[r];
int prefL = distFrom0[l], prefR = distFrom0[r];
rotateRect rectOn = rotateRect(prefR + prefL - delta, prefR + prefL + delta, prefR - prefL - delta, prefR - prefL + delta);
finalIntersect = intersection(finalIntersect, rectOn);
}
}
}
bool ans = false;
for (int l = 0; l < N-1; l++) {
for (int r = l+1; r < N; r++) {
if (finalIntersect.inside(distFrom0[l]+distFrom0[r], distFrom0[r]-distFrom0[l])) {
// cerr << "works: " << l << ", " << r << "\n";
ans = true;
}
}
}
// cerr << "ubDist: " << ubDist << ", dbg ";
// finalIntersect.dbg();
// cerr << "ans: " << ans << "\n\n";
return ans;
}
ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
test(110, N, lenSide, lenDown, costBridge);
ll lBS = 0, rBS = OO;
while (lBS < rBS-1) {
ll midBS = lBS + (rBS - lBS) / 2;
if (test(midBS, N, lenSide, lenDown, costBridge)) {
rBS = midBS;
}
else {
lBS = midBS;
}
}
return rBS;
}
