Submission #1069596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069596		Ignut	Shortcut (IOI16_shortcut)	C++17	31 / 100	2051 ms	604 KiB

shortcut

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18 + 123;

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    ll pref[n] = {};
    for (int i = 0; i < n - 1; i ++) pref[i + 1] = pref[i] + l[i];
    ll res = INF;
    for (int l = 0; l < n; l ++) {
        for (int r = l + 1; r < n; r ++) {
            ll ans = 0;
            for (int i = 0; i < n; i ++) {
                ans = max(ans, 1ll * d[i]);
                for (int j = i + 1; j < n; j ++) {
                    ll dist = min(pref[j] - pref[i], abs(pref[i] - pref[l]) + abs(pref[j] - pref[r]) + c) + d[i] + d[j];
                    ans = max(ans, dist);
                }
            }
            res = min(res, ans);
        }
    }
    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