Submission #276774

#	Time	Username	Problem	Language	Result	Execution time	Memory
276774		arayi	Shortcut (IOI16_shortcut)	C++17	38 / 100	254 ms	13824 KiB

shortcut

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

const int N = 500 + 30;

lli pr[N], aj[N][N], dz[N][N], pat, ret, a[N][N];
lli ds(int l, int r)
{
    if(l > r) swap(l, r);
    return pr[r] - pr[l];
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    for (int i = 1; i < n; i++)
        pr[i] = pr[i-1] + l[i-1];
    for (int i = 0; i < n; i++)
    {
        a[i][i] = d[i];
        aj[i][i] = d[i];
        for (int j = i + 1; j < n; j++)
            aj[i][j] = max(aj[i][j-1], ds(i, j) + d[j]), pat = max(pat, d[i] + d[j] + ds(i, j));
        dz[i][i] = d[i];
        for(int j = i - 1; j >= 0; j--)
            dz[i][j] = max(dz[i][j + 1], ds(i, j) + d[j]), pat = max(pat, d[i] + d[j] + ds(i, j));
    }
    for (int i = 1; i < n; i++)
        for(int j = 0; j < n - i; j++)
            a[j][j + i] = max(max(a[j][j + i - 1], a[j + 1][j + i]), d[j] + d[j + i] + ds(j, j + i));
    ret = pat;
    for (int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(c >= ds(i, j)) continue;
            lli sm = c + dz[i][0] + aj[j][n - 1];
            sm = max(sm, max(a[j][n-1], a[0][i]));
            int r = j;
            for(int k = j - 1; k > i; k--)
            {
                sm = max(sm, d[k] + min(c + ds(k, i), ds(k, j)) + aj[j][n - 1]);
                sm = max(sm, d[k] + min(c + ds(j, k), ds(k, i)) + dz[i][0]);
                if(ds(k, i) + c < ds(k, j))
                {
                    while(ds(k, i) + c + ds(r - 1, j) < ds(k, r - 1)) r--;
                    sm = max(sm, aj[i][k] + c + dz[j][r]);
                }
                sm = max(sm, a[k][r - 1]);
            }
            ret = min(ret, sm);
        }
    }
    return ret;
}

• 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