Submission #932323

#	Time	Username	Problem	Language	Result	Execution time	Memory
932323		teacup	Shortcut (IOI16_shortcut)	C++14	31 / 100	2063 ms	600 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ii pair<int,int>
#define vi vector<int>
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<ii> vii; 

const int MAXN=255; int ans=1e15, curr;
vi AL[MAXN];
int pref[MAXN], suff[MAXN], sum[MAXN], S, E;
int find_shortcut(int32_t n, vector<int32_t> l, vector<int32_t> d, int32_t c){
    int temp=0;
    for (int i=1; i<=n; i++){
        pref[i] = max(pref[i-1],d[i-1]-temp);
        if (i<n) temp += l[i-1];
    }
    temp=0;
    for (int i=n; i>=1; i--){
        suff[i] = max(suff[i+1],d[i-1]-temp);
        if (i>1) temp += l[i-2]; 
    }
    for (int i=0; i<n-1; i++){
        sum[i+2] = sum[i+1] + l[i];
    }
    
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            curr=0;
            for (S=i; S<j; S++){
                for (E=S+1; E<=j; E++){
                    int ds = d[S-1], de=d[E-1];
                    if (S==i) ds = pref[S]+sum[S]-sum[1];
                    if (E==j) de = suff[E]+sum[n]-sum[E];
                    curr=max(curr,ds+de+min(sum[E]-sum[S],sum[j]-sum[i]-sum[E]+sum[S]+c));
                }
            }
            for (S=1; S<=i; S++){
                for (E=S+1; E<=i; E++){
                    int ds = d[S-1], de=d[E-1];
                    curr=max(curr,ds+de+sum[E]-sum[S]);
                }
            }
            for (S=j; S<=n; S++){
                for (E=S+1; E<=n; E++){
                    int ds = d[S-1], de=d[E-1];
                    curr=max(curr,ds+de+sum[E]-sum[S]);
                }
            }
            ans = min(ans,curr);
        }
    }
    return ans;
}

• 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