#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll inf = 1e18;
ll dp[maxn], pd[maxn], ap[maxn], ad[maxn], optL[maxn], optR[maxn];
ll ans[maxn], opt[maxn], tmp[maxn];
vector<int> l, d;
int c;
ll get(int L, int R){
ll ret = max(ap[L],ad[R]);
ll Cycle = c;
for (int i = L; i < R; i++)
Cycle += l[i];
for (int i = L; i <= R; i++)
tmp[i] = d[i];
tmp[L] = dp[L], tmp[R] = pd[R];
for (int i = L; i <= R; i++){
ll now = 0;
for (int j = i+1; j <= R; j++){
now += l[j-1];
ret = max(ret, min(now+tmp[i]+tmp[j],Cycle-now+tmp[i]+tmp[j]));
}
}
return ret;
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
::l = l, ::d = d, ::c = c;
dp[0] = ap[0] = d[0];
for (int i = 1; i < n; i++){
ap[i] = max(ap[i-1], dp[i-1]+l[i-1]+d[i]);
dp[i] = max(1LL*d[i], dp[i-1]+l[i-1]);
}
pd[n-1] = ad[n-1] = d[n-1];
for (int i = n-2; i >= 0; i--){
ad[i] = max(ad[i+1], pd[i+1]+l[i]+d[i]);
pd[i] = max(1LL*d[i], pd[i+1]+l[i]);
}
ll answer = inf;
for (int i = 0; i < n-1; i++){
opt[i] = -1, ans[i] = inf;
for (int j = i+1; j < n; j++){
ll x = get(i,j);
if (x < ans[i])
ans[i] = x, optL[i] = j;
if (x == ans[i])
optR[i] = j;
}
answer = min(answer, ans[i]);
}
for (int i = 0; i < n-2; i++)
assert(optR[i+1] >= optL[i]);
return answer;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
384 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
384 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
384 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
384 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
0 ms |
384 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
384 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
384 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
0 ms |
384 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
384 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
0 ms |
384 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
384 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
0 ms |
384 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
0 ms |
384 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
0 ms |
384 KB |
n = 10, 3189 is a correct answer |
19 |
Correct |
0 ms |
384 KB |
n = 10, 7000000000 is a correct answer |
20 |
Correct |
1 ms |
436 KB |
n = 5, 12 is a correct answer |
21 |
Correct |
0 ms |
384 KB |
n = 5, 25 is a correct answer |
22 |
Correct |
0 ms |
384 KB |
n = 2, 122 is a correct answer |
23 |
Correct |
0 ms |
384 KB |
n = 10, 117 is a correct answer |
24 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 |
25 |
Halted |
0 ms |
0 KB |
- |