#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
// O(N^3) Solution [[38 pts]]
long long N, C, D[3009][3009], A[3009], B[3009], dp[3009];
long long L[6009], LL[6009], L2[6009];
long long solve_in(int cl, int cr) {
for (int i = cl; i < cr; i++) L[i - cl] = A[i]; L[cr - cl] = C;
int M = (cr - cl + 1);
for (int i = 0; i <= M * 2; i++) LL[i + 1] = LL[i] + L[i % M];
for (int i = 0; i <= M * 2; i++) L2[i] = LL[i] + B[cl + (i % M)];
long long maxn = 0; for (int i = cl; i <= cr; i++) maxn = max(maxn, B[i]);
int cx = 0; deque<pair<long long, int>> vec;
for (int i = 0; i < M; i++) {
while (LL[cx] - LL[i] <= (LL[M] / 2)) {
while (!vec.empty() && vec[vec.size() - 1].first <= L2[cx]) vec.pop_back();
vec.push_back(make_pair(L2[cx], cx));
cx++;
}
if (vec.front().second == i) vec.pop_front();
if (!vec.empty()) maxn = max(maxn, vec.front().first - (LL[i] - B[i]));
}
return maxn;
}
long long solve_out(int cl, int cr) {
long long el = 0, er = 0;
long long sl = 0; for (int i = cl - 1; i >= 0; i--) { sl += A[i]; el = max(el, sl + B[i]); }
long long sr = 0; for (int i = cr; i < N - 1; i++) { sr += A[i]; er = max(er, sr + B[i + 1]); }
long long maxn = 0;
for (int i = cl; i <= cr; i++) {
maxn = max(maxn, el + B[i] + min(D[cl][i], D[cl][cr] + C - D[cl][i]));
maxn = max(maxn, er + B[i] + min(D[cr][i], D[cl][cr] + C - D[cr][i]));
}
maxn = max(maxn, el + er + C);
return maxn;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
N = n; C = c;
for (int i = 0; i < N; i++) { if (i < N - 1) A[i] = l[i]; B[i] = d[i]; }
for (int i = 0; i < N; i++) {
long long S = 0;
for (int j = i + 1; j < N; j++) {
S += 1LL * l[j - 1];
D[i][j] = S; D[j][i] = S;
}
}
long long ans = (1LL << 60);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
long long V1 = solve_in(i, j);
long long V2 = solve_out(i, j);
//cout << "u = " << i << ", v = " << j << ", V1 = " << V1 << ", V2 = " << V2 << ", ans = " << max(V1, V2) << endl;
ans = min(ans, max(V1, V2));
}
}
return ans;
}
Compilation message
shortcut.cpp: In function 'long long int solve_in(int, int)':
shortcut.cpp:11:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = cl; i < cr; i++) L[i - cl] = A[i]; L[cr - cl] = C;
^~~
shortcut.cpp:11:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = cl; i < cr; i++) L[i - cl] = A[i]; L[cr - cl] = C;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
