Submission #64972

#	Time	Username	Problem	Language	Result	Execution time	Memory
64972		FedericoS	Shortcut (IOI16_shortcut)	C++14	0 / 100	2078 ms	248 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)
{
    //cout<<"Ok";
    for(int x=1;x<N;x++)
        L[x]=L[x-1]+l[x-1];
    for(int x=0;x<N;i++)
        D[x]=d[x];
    for(int x=1;x<N;x++)
        sin[x]=max(sin[x-1],D[x-1])+L[x]-L[x-1];
    for(int x=N-2;x>=0;x--)
        des[x]=max(des[x+1],D[x+1])+L[x+1]-L[x];


    for(i=0;i<N;i++)
        for(j=i+1;j<N;j++){
            //cout<<i<<" "<<j<<endl;
            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]);
            }
            for(int x=i;x<=j;x++){
                res=max(res,F(x,sin[i])+D[i]);
                res=max(res,F(x,des[j])+D[i]);
            }
            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