| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 137452 | Runtime_error_ | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
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>
#define ll long long
using namespace std;
const ll inf = 3e3+9 , MX = 1e18+9;
ll c,pre[inf],suf[inf],l[inf],d[inf],sum[inf],premx[inf],sufmx[inf];
ll path(ll x,ll y){
if(x>y)
swap(x,y);
return sum[y-1] - sum[x-1];
}
ll find_shortcut(int n, vector<int> L, vector<int> D, int C){
c = C;
ll ret = MX;
for(ll i=1;i<n;i++)
l[i] = L[i-1] , d[i] = D[i-1],sum[i] = sum[i-1]+l[i];
d[n] = D[n-1];
for(ll i=1;i<=n;i++){
pre[i] = max(pre[i-1]+l[i-1],d[i]);
premx[i] = max( premx[i-1] , pre[i-1] +l[i-1] + d[i] );
}
for(ll i=n;i>=1;i--){
suf[i] = max(suf[i+1]+l[i],d[i]);
sufmx[i] = max( sufmx[i+1] , suf[i+1]+l[i] +d[i] );
}
ret = sufmx[1];
for(ll x=1;x<=n;x++){
for(ll y=x+1;y<=n;y++){
ll z = 0,k = 0,diameter = pre[x]+suf[y]+c,mx1 = 0,mx2= 0;
ll mxsuf[inf]={0},mxpre[inf]={0};
for( z = x;z<=y && path(z,y)>path(z,x)+c;z++);
z--;
for( k = y ; k>=x && path(k,x) > path(k,y)+c;k-- );
k++;
for(int )
for(ll i=x;i<=z;i++)
diameter = max( diameter , path(i,x)+d[i] +c + suf[y] ),mx1 = max(mx1,path(i,x)+d[i]);
for(ll i=k ;i<=y;i++)
diameter = max( diameter , path(i,y)+d[i] +c+pre[x] ),mx2 = max(mx2,path(i,y)+d[i]);
//diameter = max(diameter,mx1+mx2+c);
if(z<x)
z = x;
if(k>y)
k = y;
diameter = max( diameter , premx[k-1] );
diameter = max( diameter ,sufmx[z+1] );
/*for(ll i=1;i<k;i++)
diameter = max(diameter , pre[i]);
for(ll i=z+1;i<=n;i++)
diameter = max(diameter , suf[i]);*/
multiset<int> s;
int l=x;
for(int i=x;i<=y;i++){
while(l<i && path(l,i)>path(i,y)+path(x,l)+c)
s.erase(s.find(-pre[l-1]+d[l])),l++;
if(!s.empty())
diameter = max(diameter , *s.rbegin()+sum[i-1]+d[i]);
s.insert(-pre[i-1]+d[i]);
}
//cout<<x<<" "<<y<<" "<<z<<" "<<k<<""<<diameter<<endl;
ret = min( ret , diameter );
}
}
return ret;
}