Submission #1042749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042749		Zicrus	Shortcut (IOI16_shortcut)	C++17	31 / 100	2052 ms	600 KiB

shortcut

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

typedef long long ll;

ll find_shortcut(int n, vector<int> l, vector<int> s, int c) {
    vector<ll> dist(n);
    vector<pair<ll, ll>> preMax(n), postMax(n);
    preMax[0] = {s[0], 0};
    for (int i = 1; i < n; i++) {
        dist[i] = dist[i-1] + l[i-1];
        preMax[i] = {dist[i] + s[i], i};
        if (preMax[i-1].first > preMax[i].first) preMax[i] = preMax[i-1];
    }
    postMax[n-1] = {dist[n-1] + s[n-1], n-1};
    for (int i = n-2; i >= 0; i--) {
        postMax[i] = {dist[i] + s[i], i};
        if (postMax[i+1].first > postMax[i].first) postMax[i] = postMax[i+1];
    }

    ll res = 1ll << 62ll;
    for (int low = 0; low < n-1; low++) {
        for (int high = low+1; high < n; high++) {
            ll dia = 0;
            for (int i = 0; i < n-1; i++) {
                for (int j = i+1; j < n; j++) {
                    ll dst = min(dist[j] - dist[i], abs(dist[i] - dist[low]) + c + abs(dist[high] - dist[j])) + s[i] + s[j];
                    dia = max(dia, dst);
                }
            }
            res = min(res, dia);
        }
    }

    return res;
}

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