#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define ll long long
const int N = 1e5+5;
ll pref[N], suff[N], p[N];
ll dis(int l, int r, vector<int> d){
if (l > r) swap(l, r);
if (l == r) return d[l];
ll x = p[r-1]+d[l]+d[r];
if (l) x -= p[l-1];
return x;
}
ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
// for (int i = 0; i < n; i++){
// ll sum = 0;
// pref[i] = suff[i] = d[i];
// for (int j = i-1; j >= 0; j--){
// sum += l[j];
// pref[i] = max(pref[i], sum+d[j]);
// }
// sum = l[i];
// for (int j = i+1; j < n; j++){
// suff[i] = max(suff[i], sum+d[j]);
// if (j == n-1) break;
// sum += l[j];
// }
// }
for (int i = 0; i < n-1; i++){
p[i] = l[i];
if (i) p[i] += p[i-1];
}
// cout << dis(0, 5, d) << '\n';
ll mn = 1e18;
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
ll mx = 0;
for (int x = 0; x < n; x++){
for (int k = 0; k < n; k++){
ll minn = dis(x, k, d);
// if (x == 0 and k == 5 and i == 3 and j == 4) cout << minn << '\n';
if (x < k) minn = min(minn, dis(x, i, d)+c+dis(k, j, d));
else minn = min(minn, dis(x, j, d)+c+dis(i, k, d));
mx = max(mx, minn);
}
}
mn = min(mn, mx);
// if (mn == 80) cout << i << " " << j << '\n';
}
}
return mn;
}
// int main()
// {
// int n, c;
// assert(2 == scanf("%d%d", &n, &c));
// std::vector<int> l(n - 1);
// std::vector<int> d(n);
// for (int i = 0; i < n - 1; i++)
// assert(1 == scanf("%d", &l[i]));
// for (int i = 0; i < n; i++)
// assert(1 == scanf("%d", &d[i]));
// long long t = find_shortcut(n, l, d, c);
// printf("%lld\n", t);
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
1 ms |
212 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
212 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
0 ms |
212 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
212 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
212 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
212 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
212 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
0 ms |
304 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
212 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
0 ms |
212 KB |
n = 3, 3000000000 is a correct answer |
14 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000 |
15 |
Halted |
0 ms |
0 KB |
- |