#include "shortcut.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 200000000000000000
#define MOD 1000000007
#define N 3005
#define MAX 10000006
#define LOG 30
#define KOK 200
using namespace std;
int l[N],d[N],n,c;
int ar[2*N];
ll ans;
ll pre[N],suf[N],mx_L[N],mx_R[N],sum[N],psum[2*N];
ll fmax(int bas,int son) {
ll res=max(pre[bas],suf[son]);
umax(res,min(1ll*c,sum[son]-sum[bas])+mx_L[bas]+mx_R[son]+sum[bas]-sum[son]);
int range=son-bas+1;
if(range>1) {
for(int i=bas;i<=son;i++) {
ar[i-bas+1]=ar[i+range-bas+1]=i;
}
for(int i=2;i<=range*2;i++) {
if(i!=range+1) psum[i]=psum[i-1]+l[ar[i-1]];
else psum[i]=psum[i-1]+c;
}
ll asum=psum[range+1];
for(int i=bas+1;i<=son;i++) {
if(sum[i]-sum[bas]>c+sum[son]-sum[i]) {
umax(res,mx_L[bas]+d[i]+c+sum[son]-sum[i]+sum[bas]);
}
else {
umax(res,mx_L[bas]+d[i]+sum[i]);
}
}
for(int i=bas;i<son;i++) {
if(sum[son]-sum[i]>c+sum[i]-sum[bas]) {
umax(res,mx_R[son]+d[i]+c+sum[i]-sum[bas]-sum[son]);
}
else {
umax(res,mx_R[son]+d[i]-sum[i]);
}
}
int ptr=1;
deque<ll> deq;
for(int i=1;i<=range;i++) {
umax(ptr,i);
if(!deq.empty() && deq.front()==psum[i]+d[ar[i]]) deq.pop_front();
while(ptr+1<=2*range && psum[ptr+1]-psum[i]<=asum-(psum[ptr+1]-psum[i])) {
ptr++;
while(!deq.empty() && deq.back()<=psum[ptr]+d[ar[ptr]]) deq.pop_back();
deq.pb(psum[ptr]+d[ar[ptr]]);
}
if(!deq.empty()) {
umax(res,deq.front()-psum[i]+d[ar[i]]);
}
}
}
return res;
}
void build() {
for(int i=1;i<n;i++) sum[i]=sum[i-1]+l[i-1];
for(int i=0;i<n;i++) mx_L[i]=mx_R[i]=-inf;
for(int i=0;i<n;i++) {
pre[i]=max((i-1>=0?pre[i-1]:0),(i-1>=0?mx_L[i-1]:-sum[i])+d[i]+sum[i]);
mx_L[i]=max((i-1>=0?mx_L[i-1]:-inf),d[i]-sum[i]);
}
for(int i=n-1;i>=0;i--) {
suf[i]=max((i+1<n?suf[i+1]:0),(i+1<n?mx_R[i+1]:sum[i])+d[i]-sum[i]);
mx_R[i]=max((i+1<n?mx_R[i+1]:-inf),d[i]+sum[i]);
}
}
void solve(int bas,int son,int pbas,int pson) {
if(bas>son) return ;
int opt=pbas;
ll res=inf;
umax(pbas,orta);
umax(pson,orta);
for(int i=pbas;i<=pson;i++) {
ll mx=fmax(orta,i);
if(res>mx) {
res=mx;
opt=i;
}
}
umin(ans,res);
//printf("%d %d %lld\n",orta,opt,res);
solve(bas,orta-1,pbas,opt);
solve(orta+1,son,opt,pson);
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
::n=n;
::c=c;
for(int i=0;i<n;i++) ::l[i]=l[i],::d[i]=d[i];
ans=inf;
build();
//printf("TRY-->%lld\n",fmax(2,7));
//for(int i=0;i<n;i++) for(int j=i;j<n;j++) umin(ans,fmax(i,j));
solve(0,n-1,0,n-1);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
n = 4, 80 is a correct answer |
2 |
Incorrect |
2 ms |
376 KB |
n = 9, incorrect answer: jury 110 vs contestant 120 |
3 |
Halted |
0 ms |
0 KB |
- |