Submission #823835

#	Time	Username	Problem	Language	Result	Execution time	Memory
823835		vnm06	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	304 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;

int N;
long long t[508], ct;
long long dst[508], calc[508];
int bst[508];

long long dist[508];
long long find_diam(int le, int ri)
{
    dist[0]=0;
    for(int i=1; i<N; i++) dist[i]=dist[i-1]+dst[i];
    if(dist[le]+ct<dist[ri])
    {
        dist[ri]=dist[le]+ct;
        for(int i=ri+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=ri-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    else if(dist[ri]+ct<dist[le])
    {
        dist[le]=dist[ri]+ct;
        for(int i=le+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=le-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    long long mst=0, v=0;
    for(int i=0; i<N; i++)
    {
        if(dist[i]+t[i]>mst)
        {
            mst=dist[i]+t[i];
            v=i;
        }
    }
    dist[v]=0;
    for(int i=v+1; i<N; i++) dist[i]=dist[i-1]+dst[i];
    for(int i=v-1; i>=0; i--) dist[i]=dist[i+1]+dst[i+1];
    if(dist[le]+ct<dist[ri])
    {
        dist[ri]=dist[le]+ct;
        for(int i=ri+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=ri-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    else if(dist[ri]+ct<dist[le])
    {
        dist[le]=dist[ri]+ct;
        for(int i=le+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=le-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    mst=0;
    for(int i=0; i<N; i++)
    {
        if(dist[i]+t[i]>mst) mst=dist[i]+t[i];
    }
    return mst+t[v];

}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    N=n;
    ct=c;
    for(int i=0; i<n; i++) t[i]=d[i];
    for(int i=1; i<n; i++) dst[i]=l[i-1];

    long long diam=find_diam(0, 0);
    for(int i=0; i<n; i++)
    {
        bst[i]=i;
        calc[i]=diam;
        for(int j=i+1; j<n; j++)
        {
            long long nd=find_diam(i, j);
            if(nd<calc[i])
            {
                calc[i]=nd;
                bst[i]=j;
            }
        }
    }
    long long mid=1e18;
    for(int i=0; i<n; i++) if(calc[i]<mid) mid=calc[i];
    return mid;
}

• 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