Submission #135943

#	Time	Username	Problem	Language	Result	Execution time	Memory
135943		Runtime_error_	Shortcut (IOI16_shortcut)	C++14	0 / 100	2 ms	376 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 3e3+9 , MX = 1e18+9;
ll pre[inf],suf[inf],l[inf],d[inf],sum[inf],premx[inf],sufmx[inf];

ll path(ll x,ll y){
    if(x>y)
        swap(x,y);
    return sum[y-1] - sum[x-1];
}

ll find_shortcut(int n, vector<int> L, vector<int> D, int c){

    ll ret = MX;
    for(ll i=1;i<n;i++)
        l[i] = L[i-1] , d[i] = D[i-1],sum[i] = sum[i-1]+l[i];
    d[n] = D[n-1];

    for(ll i=1;i<=n;i++){
        pre[i] = max(pre[i-1]+l[i-1],d[i]);
        premx[i] = max( premx[i-1] , pre[i-1] +l[i-1] + d[i] );
    }
    for(ll i=n;i>=1;i--){
        suf[i] = max(suf[i+1]+l[i],d[i]);
        sufmx[i] = max( sufmx[i+1] , suf[i+1]+l[i] +d[i] );
    }
    ret = sufmx[1];
    for(ll x=1;x<=n;x++){
        for(ll y=x+1;y<=n;y++){

            ll z = 0,k = 0,diameter = pre[x]+suf[y]+c,mx1 = 0,mx2= 0;

            for( z = x;z<=y && path(z,y)>path(z,x)+c;z++);
            z--;
            for( k = y ; k>=x && path(k,x) > path(k,y)+c;k-- );
            k++;

            for(ll i=x;i<=z;i++)
                diameter = max( diameter , path(i,x)+d[i] +c + suf[y] ),mx1 = max(mx1,path(i,x)+d[i]);

            for(ll i=k ;i<=y;i++)
                diameter = max( diameter , path(i,y)+d[i] +c+pre[x] ),mx2 = max(mx2,path(i,y)+d[i]);
            diameter = max(diameter,mx1+mx2+c);
            if(z<x)
                z = x;
            if(k>y)
                k = y;
            diameter = max( diameter , premx[k-1] );
            diameter = max( diameter ,sufmx[z+1] );
            /*for(ll i=1;i<k;i++)
                diameter = max(diameter , pre[i]);
             for(ll i=z+1;i<=n;i++)
                diameter = max(diameter , suf[i]);*/
            //cout<<x<<" "<<y<<" "<<z<<" "<<k<<""<<diameter<<endl;
            ret = min( ret , diameter );
        }
    }
    return ret;
}

• 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