oj.uz

Submission #901282

# Submission time Handle Problem Language Result Execution time Memory
901282 2024-01-09T09:13:14 Z nguyen31hoang08minh2003 Holding (COCI20_holding) C++14
88 / 110
 146 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
*/

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 5 ms 31324 KB Output is correct
3 Correct 9 ms 53848 KB Output is correct
4 Correct 6 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 33880 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 5 ms 31324 KB Output is correct
3 Correct 9 ms 53848 KB Output is correct
4 Correct 6 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 33880 KB Output is correct
8 Correct 16 ms 94812 KB Output is correct
9 Correct 15 ms 109400 KB Output is correct
10 Correct 20 ms 150872 KB Output is correct
11 Correct 23 ms 175444 KB Output is correct
12 Correct 22 ms 197212 KB Output is correct
13 Correct 146 ms 169300 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 5 ms 31324 KB Output is correct
3 Correct 9 ms 53848 KB Output is correct
4 Correct 6 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 33880 KB Output is correct
8 Correct 16 ms 94812 KB Output is correct
9 Correct 15 ms 109400 KB Output is correct
10 Correct 20 ms 150872 KB Output is correct
11 Correct 23 ms 175444 KB Output is correct
12 Correct 22 ms 197212 KB Output is correct
13 Correct 146 ms 169300 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 5 ms 35932 KB Output is correct
16 Correct 6 ms 52824 KB Output is correct
17 Correct 8 ms 55132 KB Output is correct
18 Correct 14 ms 101252 KB Output is correct
19 Correct 146 ms 169284 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 5 ms 31324 KB Output is correct
3 Correct 9 ms 53848 KB Output is correct
4 Correct 6 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 33880 KB Output is correct
8 Correct 16 ms 94812 KB Output is correct
9 Correct 15 ms 109400 KB Output is correct
10 Correct 20 ms 150872 KB Output is correct
11 Correct 23 ms 175444 KB Output is correct
12 Correct 22 ms 197212 KB Output is correct
13 Correct 146 ms 169300 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 5 ms 35932 KB Output is correct
16 Correct 6 ms 52824 KB Output is correct
17 Correct 8 ms 55132 KB Output is correct
18 Correct 14 ms 101252 KB Output is correct
19 Correct 146 ms 169284 KB Output is correct
20 Correct 23 ms 132180 KB Output is correct
21 Correct 10 ms 51288 KB Output is correct
22 Correct 14 ms 121436 KB Output is correct
23 Correct 10 ms 22344 KB Output is correct
24 Runtime error 54 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -