Submission #409024

#	Time	Username	Problem	Language	Result	Execution time	Memory
409024		urd05	Shortcut (IOI16_shortcut)	C++14	31 / 100	29 ms	1300 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

long long sum[1000000];
long long val[250][250];
const long long INF=1e16;
int c;
long long pl[1000000];
long long val2[250];
int n;

bool isp(long long k) {
    long long mmn=-INF;
    long long mmx=INF;
    long long pmn=-INF;
    long long pmx=INF;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) {
            val[i][j]=INF;
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if (sum[j]-sum[i]+pl[i]+pl[j]<=k) {
                val[i][j]=INF;
            }
            else {
                val[i][j]=k-c-pl[i]-pl[j];
                mmn=max(mmn,sum[i]-sum[j]-val[i][j]);
                mmx=min(mmx,sum[i]-sum[j]+val[i][j]);
                pmn=max(pmn,sum[i]+sum[j]-val[i][j]);
                pmx=min(pmx,sum[i]+sum[j]+val[i][j]);
            }
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if (sum[i]-sum[j]>=mmn&&sum[i]-sum[j]<=mmx&&sum[i]+sum[j]>=pmn&&sum[i]+sum[j]<=pmx) {
                return true;
            }
        }
    }
    return false;
}

long long find_shortcut(int nn,vector<int> l,vector<int> d,int cc) {
    n=nn;
    c=cc;
    sum[0]=0;
    for(int i=0;i<n-1;i++) {
        sum[i+1]=sum[i]+l[i];
    }
    for(int i=0;i<n;i++) {
        pl[i]=d[i];
    }
    long long lo=0; //impossible
    long long hi=1e16; //possible
    while (lo+1<hi) {
        long long mid=(lo+hi)/2;
        if (isp(mid)) {
            hi=mid;
        }
        else {
            lo=mid;
        }
    }
    return hi;
}

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