/*
* File created on 04/09/2022 at 10:34:35.
* Link to problem:
* Description:
* Time complexity: O()
* Space complexity: O()
* Status: ---
* Copyright: Ⓒ 2022 Francois Vogel
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear
#define int ll
#define ll long long
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e18;
int find_shortcut_act(int n, vi dist, vi at, int extraPath) {
int prefD [n];
prefD[0] = 0;
for (int i = 1; i < n; i++) prefD[i] = prefD[i-1]+dist[i-1];
int lft [n];
lft[0] = at[0];
for (int i = 1; i < n; i++) lft[i] = max(lft[i-1]+dist[i-1], at[i]);
int rgt [n];
rgt[n-1] = at[n-1];
for (int i = n-2; i >= 0; i--) rgt[i] = max(rgt[i+1]+dist[i], at[i]);
int res = inf;
for (int _ = (1LL<<60); _; _ /= 2) {
int prop = res-_;
if (prop < 0) continue;
int lastBadStart = -1;
for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) if (prefD[j]-prefD[i]+at[i]+at[j] > prop) lastBadStart = i;
bool poss = false;
for (int i = 0; i < n; i++) {
if (lft[i] > prop) continue;;
bool preIGood = true;
for (int j = 0; j < n; j++) if (at[j] > prop) preIGood = false;
for (int j = 1; j < i; j++) {
if (lft[i-1]+dist[i-1]+at[i] > prop) preIGood = false;
}
if (!preIGood) {
continue;
}
int till = n;
while (till-1 > i && till > lastBadStart && rgt[till-1]+lft[i]+min(extraPath, prefD[till-1]-prefD[i]) <= prop) till--;
if (till == n) {
continue;
}
if (till <= i+1) {
poss = true;
continue;
}
int len = till-i-1;
assert(len >= 1);
int toNext [len];
for (int j = i+1; j < till-1; j++) toNext[j-i-1] = dist[j-1];
toNext[len-1] = dist[i]+dist[till-1]+extraPath;
int prefNext [len];
prefNext[0] = toNext[0];
for (int i = 1; i < len; i++) prefNext[i] = prefNext[i-1]+toNext[i];
int locAt [len];
for (int j = 0; j < len; j++) locAt[j] = at[i+j+1];
bool ok = true;
int k = 0;
int mx = 0, sum = 0;
for (int j = 0; j < len; j++) {
if (j) {
mx -= toNext[j-1];
sum -= toNext[j-1];
}
while (sum+toNext[k] <= prefNext[len-1]/2LL) {
sum += toNext[k];
k++;
k %= len;
mx = max(mx, sum+locAt[k]);
}
if (mx+at[j] > prop) {
ok = false;
break;
}
if (locAt[j]+min(prefD[till]-prefD[j+i+1]+extraPath, prefD[j+i+1]-prefD[i])+lft[i] > prop || locAt[j]+min(prefD[till]-prefD[j+i+1], prefD[j+i+1]-prefD[i]+extraPath)+rgt[till] > prop) {
ok = false;
break;
}
}
if (ok) {
poss = true;
break;
}
}
if (poss) {
res = prop;
}
}
return res;
}
int find_shortcut(signed n, vector<signed> iL, vector<signed> iD, signed c) {
vi toL, toD;
for (int i : iL) toL.pb(i);
for (int i : iD) toD.pb(i);
return find_shortcut_act(n, toL, toD, c);
}
// signed main() {
// cin.tie(0);
// ios_base::sync_with_stdio(0);
// int n, c;
// cin >> n >> c;
// vector<signed> Il(n-1), Id(n);
// for (int i = 0; i < n-1; i++) cin >> Il[i];
// for (int i = 0; i < n; i++) cin >> Id[i];
// cout << find_shortcut(n, Il, Id, c);
// cout.flush();
// int d = 0;
// d++;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 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 |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Correct |
0 ms |
212 KB |
n = 9, 110 is a correct answer |
| 3 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 21 vs contestant 14 |
| 4 |
Halted |
0 ms |
0 KB |
- |
