Submission #99596

#	Time	Username	Problem	Language	Result	Execution time	Memory
99596		KLPP	Shortcut (IOI16_shortcut)	C++14	71 / 100	2091 ms	3624 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    lld lo,hi;
    lo=-1;
    hi=1000000000000000;
    lld level[n];
    level[0]=0;
    for(int i=1;i<n;i++)level[i]=level[i-1]+l[i-1];
    lld max_coord_sum[n];
    max_coord_sum[n-1]=level[n-1]+d[n-1];
    lld max_coord_diff[n];
    max_coord_diff[0]=d[0]-level[0];
    for(int i=1;i<n;i++){
        max_coord_diff[i]=max(max_coord_diff[i-1],d[i]-level[i]);
    }
    for(int i=n-2;i>-1;i--){
        max_coord_sum[i]=max(max_coord_sum[i+1],level[i]+d[i]);
    }
    vector<pair<lld,lld> >V;
    for(int i=0;i<n;i++){
        V.push_back(pair<lld,lld>(level[i]-d[i],-level[i]-d[i]));
    }
    lld min_case[n];
    min_case[0]=V[0].second;
    sort(V.begin(),V.end());
    while(hi-lo>1){
        lld mid=(hi+lo)/2;
        lld min_sum,max_sum;
        lld min_diff,max_diff;
        min_sum=0;
        min_diff=0;
        max_sum=1000000000000000;
        max_diff=1000000000000000;

        for(int i=0;i<n-1;i++){
            if(max_coord_sum[i+1]+d[i]-level[i]>mid){
                min_sum=max(min_sum,level[i]+d[i]+max_coord_sum[i+1]+c-mid);
                min_diff=max(min_diff,-level[i]+d[i]-mid+c+max_coord_sum[i+1]);
            }
            for(int j=i+1;j<n;j++){
                lld D=level[j]-level[i];
                if(D+d[i]+d[j]>mid){
                    lld u=mid-d[i]-d[j]-c;
                    //min_sum=max(min_sum,level[i]+level[j]-u);
                    //min_diff=max(min_diff,level[j]-level[i]-u);
                    //max_sum=min(max_sum,level[i]+level[j]+u);
                    max_diff=min(max_diff,level[j]-level[i]+u);
                }
            }
        }
        for(int i=1;i<n;i++){
            if(level[i]+d[i]+max_coord_diff[i-1]>mid){
                max_sum=min(max_sum,level[i]-d[i]+mid-c-max_coord_diff[i-1]);

            }
        }
        bool b=false;
        for(int i=0;i<n;i++){
            lld MIN=max(min_sum-level[i],min_diff+level[i]);
            lld MAX=min(max_sum-level[i],max_diff+level[i]);
            int hi1,lo1;
            lo1=i;
            hi1=n;
            while(lo1+1<hi1){
                int m=(hi1+lo1)/2;
                if(level[m]>=MIN){
                    hi1=m;
                }else lo1=m;
            }
            int hi2,lo2;
            lo2=i;
            hi2=n;
            while(lo2+1<hi2){
                int m=(hi2+lo2)/2;
                if(level[m]<=MAX){
                    lo2=m;
                }else hi2=m;
            }
            if(lo2>=hi1)b=true;
        }
        if(b)hi=mid;
        else lo=mid;
    }
    return hi;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:29:9: warning: variable 'min_case' set but not used [-Wunused-but-set-variable]
     lld min_case[n];
         ^~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3