#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!
const ll OO = (int)1e18;
struct rotateRect {
// X = R+L
// Y = R-L
ll minX, maxX;
ll minY, maxY;
rotateRect (int a, int b, int c, int d) {minX=a,maxX=b,minY=c,maxY=d;}
bool empty () {
return !(minX <= maxX && minY <= maxY);
}
void dbg () {
cerr << minX << " " << maxX << ", " << minY << " " << maxY << "\n";
}
};
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<int> 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++) {
int distLR = 0;
for (int r = l+1; r < N; r++) {
distLR += lenSide[r-1];
if (distLR + lenDown[l] + lenDown[r] > ubDist) {
int delta = ubDist - costBridge - lenDown[l] - lenDown[r];
int minL = lower_bound(distFrom0.begin(), distFrom0.end(), distFrom0[l] - delta) - distFrom0.begin();
int maxL = upper_bound(distFrom0.begin(), distFrom0.end(), distFrom0[l] + delta) - distFrom0.begin() - 1;
int minR = lower_bound(distFrom0.begin(), distFrom0.end(), distFrom0[r] - delta) - distFrom0.begin();
int maxR = upper_bound(distFrom0.begin(), distFrom0.end(), distFrom0[r] + delta) - distFrom0.begin() - 1;
// cerr << "add rect: " << minL << " " << maxL << ", " << minR << " " << maxR << "\n";
rotateRect rectOn = rotateRect(minL + minR, maxL + maxR, minL - maxR, maxL - minR);
finalIntersect = intersection(finalIntersect, rectOn);
}
}
}
// cerr << "ubDist: " << ubDist << ", dbg ";
// finalIntersect.dbg();
// cerr << "\n";
return !finalIntersect.empty();
}
ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
test(80, N, lenSide, lenDown, costBridge);
ll lBS = 0, rBS = OO;
while (lBS < rBS-1) {
int midBS = lBS + (rBS - lBS) / 2;
if (test(midBS, N, lenSide, lenDown, costBridge)) {
rBS = midBS;
}
else {
lBS = midBS;
}
}
return rBS;
}
