oj.uz

Submission #901286

# Submission time Handle Problem Language Result Execution time Memory
901286 2024-01-09T09:15:37 Z nguyen31hoang08minh2003 Holding (COCI20_holding) C++14
88 / 110
 141 ms 262144 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 8 ms 53852 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45660 KB Output is correct
6 Correct 6 ms 49756 KB Output is correct
7 Correct 10 ms 33776 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 8 ms 53852 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45660 KB Output is correct
6 Correct 6 ms 49756 KB Output is correct
7 Correct 10 ms 33776 KB Output is correct
8 Correct 13 ms 94812 KB Output is correct
9 Correct 13 ms 109532 KB Output is correct
10 Correct 21 ms 150876 KB Output is correct
11 Correct 22 ms 175452 KB Output is correct
12 Correct 24 ms 197468 KB Output is correct
13 Correct 141 ms 169552 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 8 ms 53852 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45660 KB Output is correct
6 Correct 6 ms 49756 KB Output is correct
7 Correct 10 ms 33776 KB Output is correct
8 Correct 13 ms 94812 KB Output is correct
9 Correct 13 ms 109532 KB Output is correct
10 Correct 21 ms 150876 KB Output is correct
11 Correct 22 ms 175452 KB Output is correct
12 Correct 24 ms 197468 KB Output is correct
13 Correct 141 ms 169552 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 35932 KB Output is correct
16 Correct 6 ms 52828 KB Output is correct
17 Correct 7 ms 54980 KB Output is correct
18 Correct 13 ms 101212 KB Output is correct
19 Correct 130 ms 169348 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 8 ms 53852 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45660 KB Output is correct
6 Correct 6 ms 49756 KB Output is correct
7 Correct 10 ms 33776 KB Output is correct
8 Correct 13 ms 94812 KB Output is correct
9 Correct 13 ms 109532 KB Output is correct
10 Correct 21 ms 150876 KB Output is correct
11 Correct 22 ms 175452 KB Output is correct
12 Correct 24 ms 197468 KB Output is correct
13 Correct 141 ms 169552 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 35932 KB Output is correct
16 Correct 6 ms 52828 KB Output is correct
17 Correct 7 ms 54980 KB Output is correct
18 Correct 13 ms 101212 KB Output is correct
19 Correct 130 ms 169348 KB Output is correct
20 Correct 24 ms 132316 KB Output is correct
21 Correct 10 ms 51532 KB Output is correct
22 Correct 14 ms 121448 KB Output is correct
23 Correct 14 ms 22360 KB Output is correct
24 Runtime error 45 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -