Submission #64978

#	Time	Username	Problem	Language	Result	Execution time	Memory
64978		FedericoS	Shortcut (IOI16_shortcut)	C++14	0 / 100	3 ms	376 KiB

shortcut

#include "shortcut.h"
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long int ll;

int N;
ll C;
ll L[3005];
ll D[3005];
ll ans=1e18,res;
ll i,j;
ll sin[3005],des[3005];

ll F(ll x, ll y){

    if(x>y)
        swap(x,y);

    ll a=L[y]-L[x];
    ll b=abs(L[x]-L[i])+abs(L[y]-L[j])+C;
    return min(a,b);

}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int c)
{

    C=c;

    for(int x=1;x<N;x++)
        L[x]=L[x-1]+l[x-1];
    for(int x=0;x<N;x++)
        D[x]=d[x];

    for(int x=1;x<N;x++)
        if(F(x-1,sin[x-1])+D[sin[x-1]]<D[x])
            sin[x]=x;
        else
            sin[x]=sin[x-1];

    des[N-1]=N-1;
    for(int x=N-2;x>=0;x--)
        if(F(x+1,des[x+1])+D[des[x+1]]<D[x])
            des[x]=x;
        else
            des[x]=des[x+1];

    /*for(int i=0;i<N;i++)
        cout<<sin[i]<<" ";
    cout<<endl;
    for(int i=0;i<N;i++)
        cout<<des[i]<<" ";
    cout<<endl;*/

    for(i=0;i<N;i++)
        for(j=i+1;j<N;j++){
            //cout<<i<<" "<<j<<" ";
            int y=i;
            res=0;
            for(int x=i;x<=j;x++){
                while(F(x,y)<F(x,y+1) and y<j)
                    y++;
                res=max(res,F(x,y)+D[x]+D[y]);
            }
            //cout<<res<<" ";
            for(int x=i;x<=j;x++){
                res=max(res,F(x,sin[i])+D[x]+D[sin[i]]);
                res=max(res,F(x,des[j])+D[x]+D[des[i]]);
            }
            //cout<<res<<endl;
            ans=min(ans,res);
        }

    return ans;

}

• 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