제출 #821905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821905		mosiashvililuka	Shortcut (IOI16_shortcut)	C++14	71 / 100	2070 ms	2112 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;
        }

        E=0;
        for(i=1; i<=a; i++){
            zx=max(JM[i]+1,Xlf-JM[i]);
            xc=Xrg-JM[i];

            c=JM[i]-Yrg;//JM[j]>=c
            d=JM[i]-Ylf;//JM[j]<=d

            zx=max(zx,c);xc=min(xc,d);
            if(zx>xc) continue;
            c=lower_bound(JM+1,JM+a+1,zx)-JM;
            if(c<=a&&JM[c]<=xc){
                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