Submission #409014

#	Time	Username	Problem	Language	Result	Execution time	Memory
409014		urd05	Shortcut (IOI16_shortcut)	C++14	31 / 100	2079 ms	1196 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) {
    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];
            }
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            val2[j]=INF;
        }
        for(int j=0;j<n;j++) {
            long long d=abs(sum[i]-sum[j]);
            for(int l=0;l<n;l++) {
                val2[l]=min(val2[l],val[j][l]-d);
            }
        }
        for(int j=i+1;j<n;j++) {
            bool flag=true;
            for(int l=0;l<n;l++) {
                if (abs(sum[j]-sum[l])>val2[l]) {
                    flag=false;
                    break;
                }
            }
            if (flag) {
                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