#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
#define int long long
int N, C;
vector<signed> L, D;
int find_shortcut(signed _N, std::vector<signed> _l, std::vector<signed> _d, signed _C){
L = _l, D = _d;
N = _N;
C = _C;
vector<pair<int,int>> dp (N);
pair<int,int> best = {0, -1};
for(int i = N - 1; i >= 0; i--){
dp[i] = best;
dp[i].first += D[i];
if(i == 0) break;
if(D[i] >= best.first){
best = {D[i], i};
}
best.first += L[i-1];
}
best = {0,-1};
int idx = -1;
for(int i = 0; i < N; i++){
if(dp[i] > best) best = dp[i], idx = i;
}
vector<int> dist (N);
for(int i = 1; i < N; i++){
dist[i] = dist[i-1] + L[i-1];
}
int a = idx, b = best.second;
//cout << a << " " << b << endl;
//cout << best.first << endl;
int res = LLONG_MAX;
for(int i = 0; i < N; i++){
int mx = 0;
for(int j = 0; j < N; j++){
int d = dp[j].first; // fine?
d = min(d, D[j] + abs(dist[j] - dist[i]) + C + D[b]);
mx = max(d, mx);
}
//cout << i << " " << mx << endl;
res = min(res, mx);
}
return res;
}
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:31:6: warning: unused variable 'a' [-Wunused-variable]
31 | int a = idx, b = best.second;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
256 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
0 ms |
256 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
256 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
0 ms |
256 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
0 ms |
256 KB |
n = 2, 3 is a correct answer |
7 |
Incorrect |
1 ms |
256 KB |
n = 3, incorrect answer: jury 29 vs contestant 20 |
8 |
Halted |
0 ms |
0 KB |
- |