Submission #239272

#	Time	Username	Problem	Language	Result	Execution time	Memory
239272		urd05	Shortcut (IOI16_shortcut)	C++14	23 / 100	2088 ms	384 KiB

shortcut

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

long long sum[1000000];

long long find_shortcut(int n,vector<int> l,vector<int> d,int c) {
    sum[0]=0;
    for(int i=0;i<n;i++) {
        sum[i+1]=sum[i]+l[i];
    }
    long long ret=1e15;
    for(int one=0;one<n;one++) {
        for(int two=one+1;two<n;two++) {
            long long maxi=0;
            for(int i=0;i<n;i++) {
                for(int j=i+1;j<n;j++) {
                    if (i<one) {
                        if (j<one) {
                            maxi=max(maxi,sum[j]-sum[i]+d[i]+d[j]);
                        }
                        else if (j<=two) {
                            maxi=max(maxi,min(sum[j]-sum[i]+d[i]+d[j],sum[one]-sum[i]+c+sum[two]-sum[j]+d[i]+d[j]));
                        }
                        else {
                            maxi=max(maxi,min(sum[j]-sum[i]+d[i]+d[j],sum[one]-sum[i]+c+sum[j]-sum[two]+d[i]+d[j]));
                        }
                    }
                    else if (i<=two) {
                        if (j<=two) {
                            maxi=max(maxi,min(sum[j]-sum[i]+d[i]+d[j],sum[i]-sum[one]+c+sum[two]-sum[j]+d[i]+d[j]));
                        }
                        else {
                            maxi=max(maxi,min(sum[j]-sum[i]+d[i]+d[j],sum[i]-sum[one]+c+sum[j]-sum[two]+d[i]+d[j]));
                        }
                    }
                    else {
                        maxi=max(maxi,sum[j]-sum[i]+d[i]+d[j]);
                    }
                }
            }
            ret=min(ret,maxi);
        }
    }
    return ret;
}

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