#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
ll find_shortcut(int n, vector<int> l, vector<int> s, int c) {
vector<ll> dist(n);
vector<pair<ll, ll>> preMax(n), postMax(n);
preMax[0] = {s[0], 0};
for (int i = 1; i < n; i++) {
dist[i] = dist[i-1] + l[i-1];
preMax[i] = {dist[i] + s[i], i};
if (preMax[i-1].first > preMax[i].first) preMax[i] = preMax[i-1];
}
postMax[n-1] = {dist[n-1] + s[n-1], n-1};
for (int i = n-2; i >= 0; i--) {
postMax[i] = {dist[i] + s[i], i};
if (postMax[i+1].first > postMax[i].first) postMax[i] = postMax[i+1];
}
ll res = 1ll << 62ll;
for (int low = 0; low < n-1; low++) {
for (int high = low+1; high < n; high++) {
// First search
ll mx = preMax[low].first, mxId = preMax[low].second;
ll mxFromHigh = postMax[high].first - (dist[high] - dist[low]) + min(dist[high] - dist[low], (ll)c);
if (mxFromHigh > mx) {
mx = mxFromHigh;
mxId = postMax[high].second;
}
for (int i = low+1; i < high; i++) {
ll val = min(dist[i], dist[low] + c + (dist[high] - dist[i])) + s[i];
if (val > mx) {
mx = val;
mxId = i;
}
}
// Second search
ll diaRes = 0;
ll dst = 0;
ll dia = 0;
for (int i = mxId-1; i >= 0; i--) {
dst += l[i];
ll ths = min(dst, abs(dist[mxId] - dist[high]) + c + abs(dist[low] - dist[i])) + s[i];
dia = max(dia, ths);
}
dst = 0;
for (int i = mxId+1; i < n; i++) {
dst += l[i-1];
ll ths = min(dst, abs(dist[mxId] - dist[low]) + c + abs(dist[high] - dist[i])) + s[i];
dia = max(dia, ths);
}
dia += s[mxId];
diaRes = dia;
mxId = postMax[0].second;
dst = 0;
dia = 0;
for (int i = mxId-1; i >= 0; i--) {
dst += l[i];
ll ths = min(dst, abs(dist[mxId] - dist[high]) + c + abs(dist[low] - dist[i])) + s[i];
dia = max(dia, ths);
}
dst = 0;
for (int i = mxId+1; i < n; i++) {
dst += l[i-1];
ll ths = min(dst, abs(dist[mxId] - dist[low]) + c + abs(dist[high] - dist[i])) + s[i];
dia = max(dia, ths);
}
dia += s[mxId];
diaRes = max(diaRes, dia);
mxId = preMax[n-1].second;
dst = 0;
dia = 0;
for (int i = mxId-1; i >= 0; i--) {
dst += l[i];
ll ths = min(dst, abs(dist[mxId] - dist[high]) + c + abs(dist[low] - dist[i])) + s[i];
dia = max(dia, ths);
}
dst = 0;
for (int i = mxId+1; i < n; i++) {
dst += l[i-1];
ll ths = min(dst, abs(dist[mxId] - dist[low]) + c + abs(dist[high] - dist[i])) + s[i];
dia = max(dia, ths);
}
dia += s[mxId];
diaRes = max(diaRes, dia);
res = min(res, dia);
}
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
348 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
348 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
348 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
348 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
0 ms |
348 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
348 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
348 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
348 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
348 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
348 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
0 ms |
348 KB |
n = 4, 4000000000 is a correct answer |
16 |
Incorrect |
0 ms |
396 KB |
n = 5, incorrect answer: jury 4000000000 vs contestant 3000000001 |
17 |
Halted |
0 ms |
0 KB |
- |