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 "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 5e2 + 20;
ll s[maxn] , pf[maxn] , sf[maxn] , mxp[maxn] , mxs[maxn];
int d[maxn];
ll mx[maxn][maxn];
ll fn(int a , int b)
{
if(a > b)
swap(a , b);
return s[b] - s[a];
}
long long find_shortcut(int n, std::vector<int> L, std::vector<int> D, int c)
{
for(int i = 0; i < n; i++)
{
d[i] = D[i];
if(i)
s[i] = L[i - 1] + s[i - 1];
}
memset(pf , -63 , sizeof pf);
memset(sf , -63 , sizeof sf);
memset(mxp , -63 , sizeof mxp);
memset(mxs , -63 , sizeof mxs);
for(int i = 0; i < n; i++)
{
if(i)
{
pf[i] = pf[i - 1];
mxp[i] = mxp[i - 1];
pf[i] = max(pf[i - 1] , mxp[i - 1] + d[i] + s[i]);
}
mxp[i] = max(mxp[i] , d[i] - s[i]);
}
for(int i = n - 1; i >= 0; i--)
{
sf[i] = max(sf[i + 1] , d[i] - s[i] + mxs[i + 1]);
mxs[i] = max(mxs[i + 1] , d[i] + s[i]);
}
memset(mx , -63 , sizeof mx);
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
mx[i][j] = max(mx[i][j - 1] , d[j - 1] - s[j - 1]);
ll ans = pf[n - 1];
for(int l = 0; l < n; l++)
for(int r = l + 1; r < n; r++)
{
if(c > s[r] - s[l])
continue;
ll res = max(pf[l] , sf[r]);
res = max(res , mxp[l] + mxs[r] + c - (s[r] - s[l]));
int pt = l + 1;
ll Mx = -1e18;
for(int v = l + 1; v < r; v++)
{
ll dis1 = min(s[v] - s[l] , s[r] - s[v] + c) + mxp[l] + s[l] + d[v];
ll dis2 = min(s[r] - s[v] , s[v] - s[l] + c) + mxs[r] - s[r] + d[v];
res = max(res , max(dis1 , dis2));
while(pt < v && s[v] - s[pt] >= s[r] - s[v] + c + s[pt] - s[l])
{
Mx = max(Mx , s[pt] + d[pt]);
pt++;
}
ll tmp = -1e18;
for(int u = pt; u < v; u++)
tmp = max(tmp , d[u] - s[u]);
res = max(res , s[v] + mx[pt][v] + d[v]);
res = max(res , s[r] - s[v] + c - s[l] + Mx + d[v]);
}
ans = min(ans , res);
}
return ans;
}
# | 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... |