/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;
int n;
vector<LL> p, d, pr;
LL c, best = mod * mod;
LL t[4 * 300005],D[4 * 300005];
void build(int v,int l,int r)
{
t[v] = D[v] = 0;
if (l == r)
return;
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
}
void push(int v, int l, int r)
{
if (D[v] == 0)
return;
if (l != r)
{
D[v * 2] += D[v];
D[v * 2 + 1] += D[v];
}
t[v] += D[v];
D[v] = 0;
}
void update(int v, int l, int r, int i, int j,LL val)
{
if (i > j)
return;
int m = (l + r) / 2;
push(v, l, r);
push(v * 2, l, m);
push(v * 2 + 1, m + 1, r);
if (l == i && r == j)
{
D[v] += val;
push(v, l, r);
return;
}
update(v * 2, l, m, i, min(j, m), val);
update(v * 2 + 1, m + 1, r, max(i, m + 1), j, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
LL get(int v, int l, int r, int i, int j)
{
if (i > j)
return 0;
int m = (l + r) / 2;
push(v, l, r);
push(v * 2, l, m);
push(v * 2 + 1, m + 1, r);
if (l == i && r == j)
return t[v];
return max(
get(v * 2, l, m, i, min(j, m)),
get(v * 2 + 1, m + 1, r, max(i, m + 1), j)
);
}
LL getLen(int i, int j)
{
if (i > j)
swap(i, j);
return pr[j] - pr[i];
}
LL getMaxDist(vector<LL> p,vector<LL> d,LL all=0)
{
p.PB(0);
LL sum=0,ans=0;
build(1,0,d.size()-1);
int l, r;
l = 0;
r = 1;
sum = p[r-1];
update(1,0,d.size()-1,0,0,d[0]);
while (r < d.size())
{
while (l<r && sum>all-sum)
{
LL val = get(1, 0, d.size() - 1, l, l);
update(1, 0, d.size() - 1, l, l, -val);
sum -= p[l];
l++;
}
update(1, 0, d.size() - 1, l, r-1, p[r - 1]);
if (l < r)
ans = max(ans, get(1, 0, d.size() - 1, l, r - 1) + d[r]);
update(1, 0, d.size() - 1, r, r, d[r]);
sum += p[r];
r++;
}
return ans;
}
int Main()
{
pr.resize(n);
for (int i = 1; i < n; i++)
pr[i] = pr[i - 1] + p[i - 1];
for (int l = 0; l < n; l++)
for (int r = l + 1; r < n; r++)
{
LL ans = -mod * mod;
LL mx = d[0];
ans = mx;
for (int i = 1; i < l; i++)
{
mx += p[i - 1];
ans = max(ans, mx + d[i]);
mx = max(mx, d[i]);
}
ans = max(ans, mx);
if (l - 1 >= 0)
mx += p[l - 1];
if (l - 1 >= 0)
for (int i = l; i <= r; i++)
ans = max(ans, mx + min(getLen(l, i), getLen(l, r) + c - getLen(l, i)) + d[i]);
mx += min(getLen(l, r), c);
for (int i = r + 1; i < n; i++)
{
mx += p[i - 1];
ans = max(ans, mx + d[i]);
mx = max(mx, d[i]);
}
mx = d[n - 1];
for (int i = n-2; i > r; i--)
{
mx += p[i];
ans = max(ans, mx + d[i]);
mx = max(mx, d[i]);
}
if (r < n - 1)
mx += p[r];
ans = max(ans, mx);
if (r + 1 < n)
for (int i = l; i <= r; i++)
ans = max(ans, mx + min(getLen(r, i), getLen(l, r) + c - getLen(r, i)) + d[i]);
if (l != r)
{
vector<LL> P, D;
for (int i = l; i <= r - 1; i++)
P.PB(p[i]);
for (int i = l; i <= r; i++)
D.PB(d[i]);
P.PB(c);
for (int i = l; i <= r - 1; i++)
P.PB(p[i]);
for (int i = l; i <= r; i++)
D.PB(d[i]);
ans = max(ans, getMaxDist(P, D, getLen(l, r)));
}
for (int i = 0; i < n; i++)
ans = max(ans, d[i]);
best = min(best, ans);
}
return 0;
}
LL find_shortcut(int N, vector<int> L, vector<int> D, int C)
{
n = N;
for (int i = 0; i < n - 1; i++)
p.PB(L[i]);
for (int i = 0; i < n; i++)
d.PB(D[i]);
c = C;
Main();
return best;
}
#ifdef death
int main()
{
int N, C;
vector<int> L, D;
cin >> N >> C;
for (int i = 0; i < N - 1; i++)
{
L.PB(0);
cin >> L.back();
}
for (int i = 0; i < N; i++)
{
D.PB(0);
cin >> D.back();
}
cout << find_shortcut(N, L, D, C) << endl;
return 0;
}
#endif
/*
*/
Compilation message
shortcut.cpp: In function 'long long int getMaxDist(std::vector<long long int>, std::vector<long long int>, long long int)':
shortcut.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (r < d.size())
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 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 |
384 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
2 ms |
384 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
