Submission #54012

#	Time	Username	Problem	Language	Result	Execution time	Memory
54012		Alexa2001	Shortcut (IOI16_shortcut)	C++17	38 / 100	1559 ms	4860 KiB

shortcut

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

using namespace std;

typedef long long ll;
const int Nmax = 503;

int L[Nmax], Down[Nmax], n, C;
ll S[Nmax], dist[Nmax][Nmax], op[Nmax][Nmax], dst[Nmax];

bool check(ll Lim)
{
    int i, j, x;
    for(i=1; i<=n; ++i)
        for(j=i+1; j<=n; ++j)
            if(dist[i][j] + Down[i] + Down[j] > Lim)
            {
                op[i][j] = Lim - C - Down[i] - Down[j];
                if(op[i][j] < 0) return 0;
            }
            else op[i][j] = -1;

    for(x=1; x<=n; ++x)
    {
        for(j=1; j<=n; ++j) dst[j] = LLONG_MAX;

        bool fail = 0;
        for(i=1; !fail && i<=n; ++i)
            for(j=i+1; !fail && j<=n; ++j)
                if(op[i][j] != -1)
                {
                    dst[j] = min(dst[j], op[i][j] - dist[x][i]);
                    if(dst[j] < 0) fail = 1;
                }

        if(fail) continue;

        for(i=1; i<=n; ++i)
        {
            bool ok = 1;
            for(j=1; ok && j<=n; ++j)
                if(dist[i][j] > dst[j]) ok = 0;

            if(ok) return 1;
        }
    }
    return 0;
}

ll find_shortcut(int _n, vector<int> _L, vector<int> _Down, int _C)
{
    C = _C; n = _n;

    int i, j;
    ll st, dr, mid, Sum = 0;

    for(i=1; i<=n; ++i)
        L[i] = _L[i-1], Down[i] = _Down[i-1], Sum += L[i], S[i] = S[i-1] + L[i];

    for(i=1; i<=n; ++i)
        for(j=i+1; j<=n; ++j)
            dist[i][j] = dist[j][i] = S[j-1] - S[i-1];

    st = 0; dr = Sum + (2e9);
    while(st <= dr)
    {
        mid = (st+dr)/2;
        if(check(mid)) dr = mid-1;
            else st = mid+1;
    }
    return st;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3