Submission #404679

#	Time	Username	Problem	Language	Result	Execution time	Memory
404679		MDario	Shortcut (IOI16_shortcut)	C++11	0 / 100	1 ms	204 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
long long find_shortcut(int n, vector<int> l, vector<int> d, int c){
    ll p[n], a[n], a1[n], r=1000000000000000000ll;
    p[0]=0;
    for(int i=0; i<n-1; i++){
        p[i+1]=p[i]+l[i];
    }
    a[0]=d[0];
    for(int i=1; i<n; i++){
        a[i]=max(a[i-1]+l[i-1], (ll)d[i]);
    }
    a1[n-1]=d[n-1];
    for(int i=n-2; i>=0; i--){
        a1[i]=max(a1[i+1]+l[i], (ll)d[i]);
    }
    ll r1=0;
    for(int i=0; i<n; i++){
        for(int t=i; t<n; t++){
            r1=min(a[i]+a1[t]+p[t]-p[i], a[i]+a1[t]+c);
            for(int e=i; e<=t; e++){
                r1=max(r1, max(min(a[i]+p[e]-p[i], a[i]+p[t]-p[e]+c), min(a[t]+p[t]-p[e], a[t]+p[e]-p[i]+c)));
            }
            r=min(r, r1);
        }
    }
    return r;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 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