#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long lint; int n, c; lint a[1000005], b[1000005]; bool trial(lint x){ lint ps = -1e18, pe = 1e18, ms = -1e18, me = 1e18; for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ if(b[j] - b[i] + a[i] + a[j] > x){ lint r = x - c - a[i] - a[j]; ps = max(ps, b[i] + b[j] - r); pe = min(pe, b[i] + b[j] + r); ms = max(ms, b[i] - b[j] - r); me = min(me, b[i] + b[j] + r); } } } for(int i=0; i<n; i++){ for(int j=i; j<n; j++){ if(ps <= b[i] + b[j] && b[i] + b[j] <= pe && ms <= b[i] - b[j] && b[i] - b[j] <= me){ return 1; } } } return 0; } long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { ::n = n; ::c = c; for(int i=0; i<n; i++){ a[i] = d[i]; if(i >= 1) b[i] = b[i-1] + l[i-1]; } lint s = 0, e = 1e16; while(s != e){ lint m = (s+e)/2; if(trial(m)) e = m; else s = m+1; } return s; }