#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
const ll INF = 3e18;
int n;
ll L[MAXN], ps[MAXN], D[MAXN], XT[MAXN], XS[MAXN], c, mx_xt[MAXN], mx_xs[MAXN];
inline ll dist(int i, int j) {
if (i > j) swap(i, j);
return ps[j] - ps[i];
}
inline ll check(int l, int r, int i) {
if (i == 0 || i == n + 1) return 0;
ll ans = 0;
for (int j = i + 1; j <= n; j++)
ans = max(ans, min(dist(i, j), dist(i, l) + dist(r, j) + c)+ D[i] + D[j]);
int j = i;
for (int i = 1; i < j; i++)
ans = max(ans, min(dist(i, j), dist(i, l) + dist(r, j) + c)+ D[i] + D[j]);
return ans;
}
inline ll solve(int l, int r) {
ll ans = 0;
if (c >= dist(l, r)) return INF;
ans = max(ans, check(l, r, l));
ans = max(ans, check(l, r, l + 1));
ans = max(ans, check(l, r, l - 1));
ans = max(ans, check(l, r, 1));
ans = max(ans, check(l, r, n));
ans = max(ans, check(l, r, r));
ans = max(ans, check(l, r, r + 1));
ans = max(ans, check(l, r, r - 1));
return ans;
}
ll find_shortcut(int n_, vector<int> l_, vector<int> d_, int c_) {
n = n_;
c = c_;
for (int i = 0; i < MAXN; i++)
mx_xt[i] = mx_xs[i] = -INF;
for (int i = 1; i <= n; i++) {
L[i] = l_[i - 1];
D[i] = d_[i - 1];
if (i < n) ps[i + 1] = ps[i] + L[i];
XS[i] = D[i] - ps[i];
XT[i] = D[i] + ps[i];
mx_xs[i] = max(mx_xs[i - 1], XS[i]);
}
for (int i = n; i > 0; i--)
mx_xt[i] = max(mx_xt[i + 1], XT[i]);
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ans = max(ans, dist(i, j) + D[i] + D[j]);
for (int l = 1; l <= n; l++)
for (int r = l + 1; r <= n; r++)
ans = min(ans, solve(l, r));
return ans;
}
Compilation message
railroad.cpp:1:10: fatal error: shortcut.h: No such file or directory
1 | #include "shortcut.h"
| ^~~~~~~~~~~~
compilation terminated.
