| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 25532 | mohammad_kilani | 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>
using namespace std;
long long sum[100010];
int idx1,idx2;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
for(int i=1;i<n;i++)
sum[i] = sum[i-1] + l[i-1];
long long left = 0 , right = 1e18;
long long ans = 0;
long long mx = d[0];
int last = 0 ;
idx1 = 0;
for(int i=1;i<n;i++){
long long dis = sum[i] - sum[last] +d[i] + d[last] ;
if(dis > mx){
mx = dis ;
idx1 = last;
idx2 = i ;
}
if(d[i] > sum[i] - sum[last] + d[last])
last = i ;
}
right = mx;
ans = mx;
last =0 ;
mx = d[0] ;
for(int i=1;i<=idx1;i++){
long long dis = sum[i] - sum[last] + d[i] + d[last];
if(dis > mx){
mx = dis;
}
if(d[i] > sum[i] - sum[last] + d[last])
last = i;
}
last = idx2;
mx = max(mx,d[last]);
for(int i=idx2+1;i<n;i++){
long long dis = sum[i] - sum[last] + d[i] + d[last];
if(dis > mx){
mx = dis;
}
if(d[i] > sum[i] - sum[last] + d[last])
last = i;
}
left = mx;
while(right >= left){
long long mid=(left+right)/2;
long long mx1 = 0 ;
int idx3 = idx1;
long long mx2= 0;
int idx4 = idx2;
for(int i=idx1+1;i<idx2;i++){
long long dis = sum[i] - sum[idx1] + d[i] + d[idx1];
long long dis2 = sum[idx2] - sum[i] + d[idx2] + d[i];
if(dis > mid){
if(dis2 > mx2)
{
mx2 = dis2 ;
idx4= i ;
}
}
if(dis2 > mid){
if(dis > mx1){
mx1 = dis ;
idx3 = i;
}
}
}
bool can = 1 ;
int idx5 = idx1;
int idx6 = idx2;
long long mn = 1e18;
for(int i=idx1;i<=idx3;i++){
long long dis = max((long long)(sum[i] - sum[idx1] + (long long)d[idx1]),(long long)(sum[idx3] - sum[i] + (long long)d[idx3])) + (long long)c + d[idx2];
if(dis > mid)
continue;
long long cur = mid - dis;
int j = lower_bound(sum,sum+n,sum[idx2]-cur) - sum;
if(j < idx4)
j = idx4;
long long dis2 = sum[i] - sum[idx1] + d[idx1] + c + sum[j] - sum[idx4] + d[idx4];
if(dis2 > mid)
continue;
long long dis4 = sum[idx3] - sum[i] + sum[j] - sum[idx4];
if(dis4 < mn){
mn = dis4;
idx5 = i;
idx6 = j;
}
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
long long dis1 = sum[j] - sum[i] + d[i] + d[j] ;
long long dis2 = sum[j] - sum[idx6] ;
if(dis2 < 0)
dis2*=-1;
long long dis3 = sum[i] - sum[idx5] ;
if(dis3 < 0)
dis3*=-1;
long long dis4 = dis2 + dis3 + d[i] + d[j] + c;
long long dis5 = min(dis4,dis1);
if(dis5 > mid)
can = 0 ;
}
}
if(can){
ans = mid;
right = mid - 1;
}
else
left = mid + 1;
}
return ans;
}