Submission #99592

#	Time	Username	Problem	Language	Result	Execution time	Memory
99592		KLPP	Shortcut (IOI16_shortcut)	C++14	71 / 100	2044 ms	1792 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];

    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;i++){
            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);
                }
            }
        }
        bool b=false;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(level[i]+level[j]>=min_sum && level[i]+level[j]<=max_sum && level[j]-level[i]<=max_diff && level[j]-level[i]>=min_diff){
                    b=true;
                }
            }
        }
        if(b)hi=mid;
        else lo=mid;
    }
    return hi;
}

• 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