Submission #366805

#	Time	Username	Problem	Language	Result	Execution time	Memory
366805		BartolM	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	364 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=3e5+5;

ll sum[N];
ll pref[N], suff[N];
ll until[N], later[N];

#define DEBUG 0

long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    l.insert(l.begin(), 0);
    sum[0]=0;
    for (int i=1; i<n; ++i) sum[i]=sum[i-1]+l[i];

    pref[0]=d[0];
    until[0]=d[0];
    for (int i=1; i<n; ++i) {
        until[i]=max(until[i-1]+l[i], (ll)d[i]);
        pref[i]=max(pref[i-1], d[i]+l[i]+until[i-1]);
    }

    suff[n-1]=d[n-1];
    later[n-1]=d[n-1];
    for (int i=n-2; i>=0; --i) {
        later[i]=max(later[i+1]+l[i+1], (ll)d[i]);
        suff[i]=max(suff[i+1], d[i]+l[i+1]+later[i+1]);
    }

    ll najv=-1;
    int lef=-1, rig=-1;
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            ll curr=sum[j]-sum[i]+d[i]+d[j];
            if (curr>najv || (curr==najv && j-i<rig-lef)) najv=curr, lef=i, rig=j;
        }
    }

#if DEBUG
    printf("until: ");
    for (int i=0; i<n; ++i) printf("%lld ", until[i]);
    printf("\npref: ");
    for (int i=0; i<n; ++i) printf("%lld ", pref[i]);
    printf("\nlater: ");
    for (int i=0; i<n; ++i) printf("%lld ", later[i]);
    printf("\nsuff: ");
    for (int i=0; i<n; ++i) printf("%lld ", suff[i]);
    printf("\n\n");
#endif // DEBUG

    ll sol=pref[n-1];
    for (int i=lef; i<rig; ++i) {
        for (int j=i+1; j<=rig; ++j) {
            if (sum[j]-sum[i]<=c) continue;
            ll maxi=max(pref[i], suff[j]);
            maxi=max(maxi, until[i]+later[j]+c);
#if DEBUG
            printf("i: %d, j: %d, maxi: %lld\n", i, j, maxi);
#endif

            for (int k=i+1; k<j; ++k) {
                ll curr1=min(sum[j]-sum[k]+d[k]+c+until[i], d[k]+sum[k]-sum[i]+until[i]);
                maxi=max(maxi, curr1);

                ll curr2=min(sum[k]-sum[i]+d[k]+c+later[j], d[k]+sum[j]-sum[k]+later[j]);
                maxi=max(maxi, curr2);
                #if DEBUG
                    printf("k: %d, prvo: %lld, drugo: %lld\n", k, curr1, curr2);
                #endif // DEBUG
            }
            #if DEBUG
                printf("ukupno ==================== %lld\n\n", maxi);
            #endif
            sol=min(sol, maxi);
        }
    }

    return sol;
}

• 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