#include "shortcut.h"
#include <cstdio>
#define MAX_N 1000
using namespace std;
int N;
long long C;
long long farthestLeft[MAX_N][MAX_N];
long long farthestRight[MAX_N][MAX_N];
long long worstPair[MAX_N][MAX_N];
long long sum[MAX_N];
long long D[MAX_N];
long long summ(int i, int j) {
return sum[j] - sum[i];
}
long long dist(int i, int j) {
return summ(i, j) + D[i] + D[j];
}
long long farthestPair(int a, int b) {
long long ans;
// op1: i,j outside the cycle, same side
long long op1 = max(worstPair[0][a], worstPair[b][N - 1]);
//printPair(op1, op1);
ans = op1;
// op2: i,j outside the cycle, opposite sides
if (a > 0 && b < N - 1) {
long long K2 = min( C, summ(a, b) );
long long op2 = farthestLeft[a][0] + farthestRight[b][N - 1] + K2;
ans = max(ans, op2);
//printPair(op2, op2);
}
// op3: i, inside; j, outside
if (b < N - 1) {
for (int i = a; i <= b; i++) {
long long Ki = min(summ(a, i) + C, summ(i, b)) + D[i];
ans = max(ans, Ki + farthestRight[b][N - 1]);
//printPair(i, Ki + farthestRight[b][N - 1]);
}
}
// op4: i, outside; j, inside
if (a > 0) {
for (int j = a; j <= b; j++){
long long Kj = min(summ(a, j), summ(j, b) + C) + D[j];
ans = max(ans, Kj + farthestLeft[a][0]);
//printPair(j, Kj + farthestLeft[a][0]);
}
}
// op5: both i and j inside
int j = a;
long long opA, opB;
long long S = summ(a, b);
//printPair(99, sum[3]);
for (int i = a; i <= b; i++) {
opA = summ(i, j);
opB = S - opA + C;
//printISum(i, opA, opB);
while (j <= b && opA <= opB) {
j++;
opA = summ(i, j);
opB = S - opA + C;
//printJSum(j, opA, opB);
}
//op5.1
//printISum(i, 99, farthestRight[i][j - 1] + D[i]);
if (i < j - 1)
ans = max(ans, farthestRight[i][j - 1] + D[i]);
//op5.2
if (j <= b)
ans = max(ans, summ(a, i) + C + D[i] + max(farthestLeft[b][j], D[b]));
}
return ans;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
// init
N = n;
C = (long long) c;
for (int i = 0; i < n; i++) {
D[i] = (long long) d[i];
}
for (int i = 1; i < n; i++)
sum[i] = sum[i - 1] + (long long) l[i - 1];
for (int i = 0; i < n; i++) {
// farthestLeft[i][i] = D[i];
for (int j = i - 1; j >= 0; j--)
farthestLeft[i][j] = max(farthestLeft[i][j + 1], dist(j, i) - D[i]);
}
for (int i = 0; i < n; i++) {
// farthestRight[i][i] = D[i];
for (int j = i + 1; j < n; j++)
farthestRight[i][j] = max(farthestRight[i][j - 1], dist(i, j) - D[i]);
}
for (int k = 1; k < n; k++) {
int i = 0;
for (int j = i + k; j < n; i++, j++) {
worstPair[i][j] = max(worstPair[i][j - 1], worstPair[i + 1][j]);
worstPair[i][j] = max(worstPair[i][j], dist(i, j));
}
}
// find best pair to place the shortcut
long long ans = -1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (ans == -1 || farthestPair(i, j) < ans) {
ans = farthestPair(i, j);
//printPair(i, j);
}
}
}
return ans;
}
