#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll inf = 1e18, N = 1000;
vector<pll> g[N];
ll d[N][N], msf[N], mpr[N];
long long find_shortcut(int n, vector<int> l, vector<int> dt, int c) {
for (int i = 0; i < n - 1; i++) {
g[i].push_back({i + 1, l[i]});
g[i + 1].push_back({i, l[i]});
}
for (int i = 0; i < n; i++) {
g[i].push_back({i + n, dt[i]});
g[i + n].push_back({i, dt[i]});
}
for (int i = 0; i < 2 * n; i++) {
for (int j = 0; j < 2 * n; j++) d[i][j] = inf;
priority_queue<pll> s;
d[i][i] = 0;
s.push({0, i});
while (sz(s)) {
auto [dt, u] = s.top();
s.pop();
if (-dt != d[i][u]) continue;
for (auto [to, w]: g[u]) {
if (d[i][to] > d[i][u] + w) {
d[i][to] = d[i][u] + w;
s.push({-d[i][to], to});
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = n; j <= i + n; j++) {
mpr[i] = max(mpr[i], d[i][j]);
}
for (int j = i + n; j < 2 * n; j++) {
msf[i] = max(msf[i], d[i][j]);
}
}
ll ans = inf;
for (int x = 0; x < n; x++) {
for (int y = x + 1; y < n; y++) {
ll res = 0;
for (int a = n; a < 2 * n; a++) {
if (a - n <= y) {
ll v = min(d[a][y], d[a][x] + c);
v += msf[y];
res = max(res, v);
}
if (a - n >= x) {
ll v = min(d[a][x], d[a][y] + c);
v += mpr[x];
res = max(res, v);
}
}
ans = min(ans, res);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
0 ms |
348 KB |
n = 9, 110 is a correct answer |
3 |
Incorrect |
0 ms |
348 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
4 |
Halted |
0 ms |
0 KB |
- |