oj.uz

Submission #903980

# Submission time Handle Problem Language Result Execution time Memory
903980 2024-01-11T15:56:40 Z nguyen31hoang08minh2003 Holding (COCI20_holding) C++14
110 / 110
 44 ms 10740 KB 
#include <bits/stdc++.h>

/*

    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

    Thus, the elements which are originally to the left of the interval [L, R]
        should have final positions to the left to
        final positions of the elements which are originally to the right of the interval [L, R]



*/

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, INF = 0X3F3F3F3F, NINF = 0XC0C0C0C0;

int result = INF, N, L, R, K, A[MAX_N], leftCost[MAX_N][MAX_K], rightCost[MAX_N][MAX_K], newCost[MAX_N][MAX_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 j = 0, i, k, d; j < L; ++j) {
        for (i = L; i <= R; ++i)
            for (k = 0; k <= K; ++k) {
                newCost[i][k] = newCost[i - 1][k] + A[i];
                if (j >= 1) {
                    d = i - j;
                    minimize(newCost[i][k], leftCost[i][k]);
                    if (k >= d)
                        minimize(newCost[i][k], leftCost[i - 1][k - d] + A[j]);
                }
            }
        for (i = L; i <= R; ++i)
            for (k = 0; k <= K; ++k)
                leftCost[i][k] = newCost[i][k];
    }

    for (int j = N + 1, i, k, d; j > R; --j) {
        for (i = R; i >= L; --i)
            for (k = 0; k <= K; ++k) {
                newCost[i][k] = newCost[i + 1][k] + A[i];
                if (j <= N) {
                    d = j - i;
                    minimize(newCost[i][k], rightCost[i][k]);
                    if (k >= d)
                        minimize(newCost[i][k], rightCost[i + 1][k - d] + A[j]);
                }
            }
        for (i = R; i >= L; --i)
            for (k = 0; k <= K; ++k)
                rightCost[i][k] = newCost[i][k];
    }

    minimize(result, min(leftCost[R][K], rightCost[L][K]));

    for (int i = L, k; i < R; ++i)
        for (k = 0; k <= K; ++k)
            minimize(result, leftCost[i][k] + rightCost[i + 1][K - k]);

    cout << result << '\n';

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 10740 KB Output is correct
4 Correct 2 ms 10600 KB Output is correct
5 Correct 1 ms 10600 KB Output is correct
6 Correct 1 ms 10720 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 10740 KB Output is correct
4 Correct 2 ms 10600 KB Output is correct
5 Correct 1 ms 10600 KB Output is correct
6 Correct 1 ms 10720 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 19 ms 5464 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 10740 KB Output is correct
4 Correct 2 ms 10600 KB Output is correct
5 Correct 1 ms 10600 KB Output is correct
6 Correct 1 ms 10720 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 19 ms 5464 KB Output is correct
14 Correct 1 ms 4696 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 12 ms 5468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 10740 KB Output is correct
4 Correct 2 ms 10600 KB Output is correct
5 Correct 1 ms 10600 KB Output is correct
6 Correct 1 ms 10720 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 2 ms 4696 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 19 ms 5464 KB Output is correct
14 Correct 1 ms 4696 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 12 ms 5468 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 2 ms 2396 KB Output is correct
24 Correct 4 ms 8796 KB Output is correct
25 Correct 44 ms 10324 KB Output is correct