이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
vector<ll> prefix(n);
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i-1] + l[i-1];
}
vector<vector<ll>> maxFrom(n, vector<ll>(n));
ll ans = 0;
for (int i = 0; i < n; i++) {
auto& m = maxFrom[i];
for (int j = i+1; j < n; j++) {
ll x = prefix[j] - prefix[i] + d[j];
ans = max(ans, x + d[i]);
m[j] = max(m[j-1], x);
}
for (int j = i-1; j >= 0; j--) {
ll x = prefix[i] - prefix[j] + d[j];
ans = max(ans, x + d[i]);
m[j] = max(m[j+1], x);
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (prefix[j] - prefix[i] <= c) continue;
ll a = 0;
int s = i;
while (s + 1 <= j && prefix[s + 1] - prefix[i] < c + prefix[j] - prefix[s + 1]) {
s++;
}
for (int b = 0; b <= i; b++) {
a = max(a, d[b] + maxFrom[b][i]);
a = max(a, d[b] + prefix[i] - prefix[b] + c + max((ll) d[j], maxFrom[j][n-1]));
}
for (int b = j; b < n; b++) {
a = max(a, d[b] + maxFrom[b][n-1]);
a = max(a, d[b] + prefix[j] - prefix[b] + c + max((ll) d[i], maxFrom[i][0]));
}
// if (i == 1 && j == 3) {
// cout << a << endl;
// }
for (int b = i+1; b < j; b++) {
s = max(s, b);
while (s >= b && s+1 <= j && prefix[s+1] - prefix[b] < c + prefix[j] - prefix[s+1] + prefix[b] - prefix[i]) {
s++;
if (s == j) s = i;
}
while (s < b && c + prefix[j] - prefix[b] + prefix[s] - prefix[i] < prefix[b] - prefix[s]) {
s++;
}
if (s > b) {
// a = max(a, maxFrom[b][i]);
a = max(a, d[b] + prefix[b] - prefix[i] + max((ll) d[i], maxFrom[i][0]));
a = max(a, d[b] + prefix[b] - prefix[i] + c + max((ll) d[j], max(maxFrom[j][s+1], maxFrom[j][n-1])));
a = max(a, d[b] + maxFrom[b][s]);
} else if (s == i) {
a = max(a, d[b] + maxFrom[b][n-1]);
a = max(a, d[b] + maxFrom[b][0]);
} else {
a = max(a, d[b] + prefix[j] - prefix[b] + max((ll) d[j], maxFrom[j][n-1]));
a = max(a, d[b] + prefix[j] - prefix[b] + c + max((ll) d[i], max(maxFrom[i][s], maxFrom[i][0])));
}
}
// cout << i << ' ' << j << endl;
// cout << a << endl;
ans = min(ans, a);
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |