#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3000;
const ll INF = 1e18;
int n;
ll pf[MAXN], sf[MAXN]; int p[MAXN], pfPai[MAXN], sfPai[MAXN];
ll pos[MAXN+2];
ll find_shortcut(int N, vector<int> l, vector<int> d, int c) {
n = N;
pf[0] = d[0]; pfPai[0] = 0;
for (int i=0; i<n-1; i++) {
pfPai[i+1] = (d[i+1] >= pf[i]+l[i] ? i+1 : pfPai[i]);
pf[i+1] = max(
(ll)d[i+1],
pf[i] + l[i]
);
}
sf[n-1] = d[n-1]; sfPai[n-1] = n-1;
for (int i=n-2; i>=0; i--) {
sfPai[i] = (d[i] >= sf[i+1] + l[i] ? i : sfPai[i+1]);
sf[i] = max(
(ll)d[i],
sf[i+1] + l[i]
);
}
int center = 0;
for (int i=0; i<n-1; i++) {
if (pf[i] + sf[i+1] + l[i] > pf[center] + sf[center+1] + l[center])
center = i;
}
n = 0; pos[n++] = 0;
bool left = false, right = false;
if (d[pfPai[center]] > 0) {
left = true;
p[n] = pfPai[center];
pos[n++] = d[pfPai[center]];
}
for (int i=pfPai[center]; i<sfPai[center+1]; i++) {
pos[n] = pos[n-1] + l[i];
p[n] = i+1;
n++;
}
if (d[sfPai[center+1]] > 0) {
right = true;
pos[n] = pos[n-1] + d[sfPai[center+1]];
n++;
}
// for (int i=0; i<n; i++) {
// cout << pos[i] << ' ';
// }
// cout << endl;
ll ans = pf[center] + sf[center + 1] + l[center];
for (int i=left; i<n-right; i++) {
for (int j=i+1; j<n-right; j++) {
// cout << i << ' ' << j << ' ' << pos[j] - pos[i] << endl;
if (pos[j] - pos[i] <= c) continue;
ll res = max({
pos[i] + c + pos[n-1] - pos[j],
(p[i] > 0 ? pf[p[i]-1] + l[p[i]-1] + d[p[i]] : 0LL),
(p[j] < N-1 ? sf[p[j]+1] + l[p[j]] + d[p[j]] : 0LL)
});
// cout << pos[i] << ' ' << c << ' ' << pos[n-1] << ' ' << pos[j] << endl;
for (int k=i+1; k<j; k++) {
// cout << max(min(pos[k], pos[j]-pos[k]+c+pos[i]),
// min(pos[n-1]-pos[k], pos[k]-pos[i]+c+pos[n-1]-pos[j])) + d[p[k]] << ' ';
res = max({
res,
min(pos[k], pos[j]-pos[k]+c+pos[i]) + d[p[k]],
min(pos[n-1]-pos[k], pos[k]-pos[i]+c+pos[n-1]-pos[j]) + d[p[k]]
});
}
// cout << endl;
// cout << i << ' ' << j << ' ' << res << endl;
ans = min(ans, res);
}
}
return ans;
}
Compilation message (stderr)
shortcut.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |