#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct prefix_sums{
vector<ll> sums;
prefix_sums(int n, vector<int> nums){
sums = vector<ll>(n);
for (int i=1; i<n; i++){
sums[i] = sums[i-1] + nums[i-1];
}
}
ll query(int l, int r){
if (r < l) swap(l, r);
return sums[r] - sums[l];
}
};
ll calc_dist(ll start, ll end, ll i, ll j, ll c, prefix_sums sums, vector<int> d){
ll dist = sums.query(start, end) + d[start] + d[end]; // ohne Express Strecke
dist = min(dist, sums.query(start, i) + c + sums.query(j, end) + d[start] + d[end]);
swap(i, j);
dist = min(dist, sums.query(start, i) + c + sums.query(j, end) + d[start] + d[end]);
return dist;
}
ll find_diameter (int n, prefix_sums sums, vector<int> d, int i_express, int j_express, ll c, int diameter_l, int diameter_r){
ll diameter_len = 0;
for (int i=0; i<n; i++){
if (i != diameter_l){
diameter_len = max(diameter_len, calc_dist(i, diameter_l, i_express, j_express, c, sums, d));
}
if (i != diameter_r){
diameter_len = max(diameter_len, calc_dist(i, diameter_r, i_express, j_express, c, sums, d));
}
}
/*for (int i=0; i<n; i++){
for (int j=i+1; j<n; j++){
diameter_len = max(diameter_len, calc_dist(i, j, i_express, j_express, c, sums, d));
}
}*/
/*ll start = 0, diameter_len = 0;
for (int i=1; i<n; i++){
ll dist = calc_dist(0, i, i_express, j_express, c, sums, d);
cerr << i << ": " << dist << endl;
if (dist > diameter_len){
start = i;
diameter_len = dist;
}
}
cerr << start << endl;
for (int i=0; i<n; i++){
if (i == start) continue;
ll dist = calc_dist(start, i, i_express, j_express, c, sums, d);
if (dist > diameter_len){
diameter_len = dist;
}
}*/
//if (left_diameter > right_diameter) swap(left_diameter, right_diameter);
return diameter_len;
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
prefix_sums sums = prefix_sums(n, l);
int start, end = 0, diameter_len = 0;
for (int i=1; i<n; i++){
ll dist = sums.query(0, i) + d[0] + d[i];
cerr << i << ": " << dist << endl;
if (dist > diameter_len){
start = i;
diameter_len = dist;
}
}
cerr << start << endl;
for (int i=0; i<n; i++){
if (i == start) continue;
ll dist = sums.query(start, i) + d[start] + d[i];
if (dist > diameter_len){
diameter_len = dist;
}
}
if (start > end) swap(start, end);
ll best_result = 1e18;
for (int i=start; i<=end; i++){
for (int j=i+1; j<=end; j++){
//cerr << i << ", " << j << ": " << endl;
//cerr << find_diameter(n, sums, d, i, j, c) << endl;
best_result = min(best_result, find_diameter(n, sums, d, i, j, c, start, end));
}
}
//cerr << find_diameter(n, sums, d, 0, 6, c);
return best_result;
}
