Submission #530848

#	Time	Username	Problem	Language	Result	Execution time	Memory
530848		Cyanmond	Shortcut (IOI16_shortcut)	C++17	23 / 100	2072 ms	296 KiB

shortcut

#include <bits/stdc++.h>

using i64 = long long;
template <typename T> using Vec = std::vector<T>;

constexpr int inf = 1100000000;
constexpr i64 inf64 = 2000000000000000000;

template <typename T> bool setmin(T &a, const T v) {
    if (a > v) {
        a = v;
        return true;
    }
    return false;
}

template <typename T> bool setmax(T &a, const T v) {
    if (a < v) {
        a = v;
        return true;
    }
    return false;
}

long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int C) {
    std::vector<i64> S(N);
    for (int i = 0; i < N - 1; ++i) S[i + 1] = S[i] + L[i];

    i64 ans = inf64;
    for (int a = 0; a < N; ++a) {
        for (int b = a + 1; b < N; ++b) {
            i64 res = 0;
            for (int x = 0; x < N; ++x) {
                for (int y = x + 1; y < N; ++y) {
                    i64 c1 = D[x] + D[y];
                    i64 c2 = S[y] - S[x];
                    i64 c3 = (y > b) ? (S[y] - S[b]) : (S[b] - S[y]);
                    i64 c4 = (x > a) ? (S[x] - S[a]) : (S[a] - S[x]);
                    setmax(res, c1 + std::min(c2, c3 + c4 + C));
                }
            }
            setmin(ans, res);
        }
    }

    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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