Submission #821880

#	Time	Username	Problem	Language	Result	Execution time	Memory
821880		mosiashvililuka	Shortcut (IOI16_shortcut)	C++14	71 / 100	2058 ms	2132 KiB

shortcut

#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
const long long ZM=1000009,N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,C,JM[ZM],dis[ZM],lef,rig,mid,X,Y,Xlf,Xrg,Ylf,Yrg,E;
long long find_shortcut(int Nn, std::vector<int> Ll, std::vector<int> Dd, int Cc)
{
    a=Nn;C=Cc;
    JM[1]=0;
    for(i=2; i<=a; i++){
        JM[i]=JM[i-1]+Ll[i-2];
    }
    for(i=1; i<=a; i++){
        dis[i]=Dd[i-1];
    }

    lef=0;rig=N;
    while(1){
        if(lef+1>=rig) break;
        mid=(lef+rig)/2;
        Xlf=Ylf=-N;Xrg=Yrg=N;E=0;
        for(i=1; i<=a; i++){
            for(j=i+1; j<=a; j++){
                if(JM[j]-JM[i]+dis[i]+dis[j]<=mid) continue;
                c=JM[i];d=JM[j];
                X=c+d;Y=c-d;//45-it saatis isris mimartulebit
                zx=mid-dis[i]-dis[j]-C;
                if(zx<0){
                    E=1;break;
                }
                Xlf=max(Xlf,X-zx);
                Xrg=min(Xrg,X+zx);
                Ylf=max(Ylf,Y-zx);
                Yrg=min(Yrg,Y+zx);
            }
            if(E==1) break;
        }
        if(Xlf>Xrg||Ylf>Yrg) E=1;
        if(E==1){
            lef=mid;
            continue;
        }

        /*for(i=1; i<=a; i++){
            if(JM[i]>=Xlf){
                if(JM[i]>Xrg) E=1;
                break;
            }
        }
        for(i=1; i<=a; i++){
            if(JM[i]>=Ylf){
                if(JM[i]>Yrg) E=1;
                break;
            }
        }*/
        E=0;
        for(i=1; i<=a; i++){
            for(j=i+1; j<=a; j++){
                c=JM[i];d=JM[j];
                X=c+d;Y=c-d;
                if(X>=Xlf&&X<=Xrg&&Y>=Ylf&&Y<=Yrg){
                    E=1;
                }
            }
            if(E==1) break;
        }
        if(E==0){
            lef=mid;
        }else{
            rig=mid;
        }
    }
    return rig;
}

• 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