// #pragma once
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18 + 100;
const int maxn = 1e6 + 100;
const int maxl = 20;
int n, C;
ll a[maxn];
ll b[maxn];
ll p[2][maxl][maxn];
int lg[maxn];
ll ans[3030][3030];
// struct asd{
// ll ans;
// ll a, b;
// } d[maxn * 4];
// asd f(asd a, asd b){
// asd c;
// c.a = max(a.a, b.a);
// c.b = max(a.b, b.b);
// c.ans = max({a.ans, b.ans, a.a + b.b});
// return c;
// }
// void build(int v = 1, int tl = 1, int tr = n){
// if(tl == tr){
// d[v] = {0, b[tl] - a[tl], b[tl] + a[tl]};
// } else{
// int mid = (tl + tr) >> 1;
// build(v<<1, tl, mid);
// build(v<<1|1, mid+1, tr);
// d[v] = f(d[v<<1], d[v<<1|1]);
// }
// }
// asd ans(int l, int r, int v = 1, int tl = 1, int tr = n){
// if(tr < l || tl > r) return {0, -INF, -INF};
// if(l <= tl && tr <= r) return d[v];
// int mid = (tl + tr) >> 1;
// return f(ans(l, r, v<<1, tl, mid)
// , ans(l, r, v<<1|1, mid+1, tr));
// }
ll get(int l, int r, int c){
if(l > r) return -INF;
int k = lg[r - l + 1];
return max(p[c][k][l], p[c][k][r-(1<<k)+1]);
}
bool ok(ll x){
// int tl = 0, tr = n + 1;
// while(tl < n && ans[1][tl+1] <= x) tl++;
// while(tr > 1 && ans[tr-1][n] <= x) tr--;
for(int l = 1; l < n; l++){
for(int r = l + 1; r <= n; r++){
bool ok = 1;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(b[j] + b[i] + a[j] - a[i] <= x) continue;
if(i > l && i < r && j >= r){
if(b[i] + b[j] + a[i] - a[l] + C + a[j] - a[r] > x) ok = 0;
} else if(i <= l){
if(j >= r){
if(b[j] + b[i] + a[j] - a[i] - a[r] + a[l] + C > x) ok = 0;
} else if(j > l){
if(b[j] + b[i] + a[r] - a[j] + a[l] - a[i] + C > x) ok = 0;
}
} else ok = 0;
}
}
if(ok) return 1;
}
}
return 0;
}
long long find_shortcut(int N, std::vector <int> l, std::vector <int> d, int c){
n = N; C = c;
for(int i = 1; i <= n; i++){
b[i] = d[i-1];
if(i == 1) continue;
a[i] = a[i-1] + l[i - 2];
}
for(int i = 1; i <= n; i++){
p[0][0][i] = b[i] - a[i];
p[1][0][i] = b[i] + a[i];
if(i > 1) lg[i] = lg[i >> 1] + 1;
}
for(int c = 0; c < 2; c++){
for(int k = 1; k <= lg[n]; k++){
for(int i = 1; i + (1<<k) - 1 <= n; i++){
p[c][k][i] = max(p[c][k-1][i], p[c][k-1][i+(1<<(k-1))]);
}
}
}
for(int l = n - 1; l > 0; l--){
for(int r = l + 1; r <= n; r++){
ans[l][r] = max(ans[l][r-1],
b[r] + a[r] + get(l, r-1, 0));
}
}
ll res = 0;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
res = max(res, b[i] + b[j] + a[j] - a[i]);
}
}
for(ll l = 0, r = res - 1; l <= r;){
ll mid = (l + r) >> 1;
if(!ok(mid)) l = mid + 1;
else r = mid - 1, res = mid;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14684 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
18876 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
