Submission #901286

#	Time	Username	Problem	Language	Result	Execution time	Memory
901286		nguyen31hoang08minh2003	Holding (COCI20_holding)	C++14	88 / 110	141 ms	262144 KiB

holding

#include <bits/stdc++.h>

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

using namespace std;

constexpr int MAX_N = 102, MAX_K = 1E4 + 4;
constexpr long long INF = 0X3F3F3F3F3F3F3F3F, NINF = 0XC0C0C0C0C0C0C0C0;

int N, L, R, K, A[MAX_N];
long long result = INF;

/*

    Consider the problem

        Give n integers a[1], ..., a[n]
        and another n integers b[1], ..., b[n]

        Find permutations of (1, ..., n), p and q
            such that |a[p[1]] - b[q[1]]| + ... + |a[p[n]] - b[q[n]]|
                is minimum

        Solution:
            Sort a and b

    If we want to bring m elements whose indices greater than R into range [L, R]
        then we should allocate them in range [R - m + 1, R]

    If we want to bring m elements whose indices smaller than L into range [L, R]
        then we should allocate them in range [L, L + m - 1]
*/

long long findRightOptimalCost(const int i, const int j, const int k) {
    static long long minimum[MAX_N][MAX_N][MAX_K];
    static bool visited[MAX_N][MAX_N][MAX_K];

    if (k < 0)
        return INF;

    if (i > R)
        return 0;

    if (!visited[i][j][k]) {
        visited[i][j][k] = true;
        minimum[i][j][k] = findRightOptimalCost(i + 1, j, k) + A[i];
        if (j <= N) {
            const int d = j - i;
            minimize(minimum[i][j][k], findRightOptimalCost(i, j + 1, k));
            if (k >= d)
                minimize(minimum[i][j][k], findRightOptimalCost(i + 1, j + 1, k - d) + A[j]);
        }
    }
    return minimum[i][j][k];
}

long long findLeftOptimalCost(const int i, const int j, const int k) {
    static long long minimum[MAX_N][MAX_N][MAX_K];
    static bool visited[MAX_N][MAX_N][MAX_K];

    if (k < 0)
        return INF;

    if (i < L)
        return 0;

    if (!visited[i][j][k]) {
        visited[i][j][k] = true;
        minimum[i][j][k] = findLeftOptimalCost(i - 1, j, k) + A[i];
        if (j >= 1) {
            const int d = i - j;
            minimize(minimum[i][j][k], findLeftOptimalCost(i, j - 1, k));
            if (k >= d)
                minimize(minimum[i][j][k], findLeftOptimalCost(i - 1, j - 1, k - d) + A[j]);
        }
    }
    return minimum[i][j][k];
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> L >> R >> K;

    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    for (int i = L, j, k; i <= R; ++i)
        for (j = 0; j < L; ++j)
            for (k = 0; k <= K; ++k)
                findLeftOptimalCost(i, j, k);

    for (int i = R, j, k; i >= L; --i)
        for (j = N; j > R; --j)
            for (k = 0; k <= K; ++k)
                findRightOptimalCost(i, j, k);

    minimize(result, min(findLeftOptimalCost(R, L - 1, K), findRightOptimalCost(L, R + 1, K)));

    for (int i = L, k; i < R; ++i)
        for (k = 0; k <= K; ++k)
            minimize(result, findLeftOptimalCost(i, L - 1, k) + findRightOptimalCost(i + 1, R + 1, K - k));

    cout << result << '\n';

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 0 / 22