This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
ll find_shortcut(int n, vector<int> l, vector<int> s, int c) {
vector<ll> dist(n), preMax(n), postMax(n);
preMax[0] = s[0];
for (int i = 1; i < n; i++) {
dist[i] = dist[i-1] + l[i-1];
preMax[i] = max(preMax[i-1] + l[i-1], (ll)s[i]);
}
postMax[n-1] = s[n-1];
for (int i = n-2; i >= 0; i--) {
postMax[i] = max(postMax[i+1] + l[i], (ll)s[i]);
}
ll res = 1ll << 62ll;
for (int low = 0; low < n-1; low++) {
for (int high = low+1; high < n; high++) {
if (c >= dist[high] - dist[low]) continue;
// Left to right
ll dia = c + preMax[low] + postMax[high];
// Left to mid
ll id = low+1; // First id where it's better to take the highway
while (id < high) {
if (dist[id] - dist[low] >= c + dist[high] - dist[id]) break;
// Normal route
dia = max(dia, preMax[low] + dist[id] - dist[low] + s[id]);
id++;
}
for (int i = id; i < high; i++) {
dia = max(dia, preMax[low] + c + dist[high] - dist[i] + s[i]);
}
// Right to mid
id = high-1; // First id where it's better to take the highway
while (id > low) {
if (dist[high] - dist[id] >= c + dist[id] - dist[low]) break;
// Normal route
dia = max(dia, postMax[high] + dist[high] - dist[id] + s[id]);
id--;
}
for (int i = id; i > low; i--) {
dia = max(dia, postMax[high] + c + dist[i] - dist[low] + s[i]);
}
// Mid
for (int i = low; i < high; i++) {
for (int j = i+1; j <= high; j++) {
ll dst = min(dist[j] - dist[i], abs(dist[i] - dist[low]) + c + abs(dist[high] - dist[j])) + s[i] + s[j];
dia = max(dia, dst);
}
}
res = min(res, dia);
}
}
return res;
}
# | 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... |