oj.uz

Submission #901287

# Submission time Handle Problem Language Result Execution time Memory
901287 2024-01-09T09:18:02 Z nguyen31hoang08minh2003 Holding (COCI20_holding) C++14
88 / 110
 119 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 = 105, MAX_K = 1E4 + 5;
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 || j > N + 1)
        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 || j < 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];

    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 8536 KB Output is correct
2 Correct 3 ms 29276 KB Output is correct
3 Correct 7 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 5 ms 49756 KB Output is correct
7 Correct 8 ms 29528 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 3 ms 29276 KB Output is correct
3 Correct 7 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 5 ms 49756 KB Output is correct
7 Correct 8 ms 29528 KB Output is correct
8 Correct 20 ms 117596 KB Output is correct
9 Correct 17 ms 133980 KB Output is correct
10 Correct 19 ms 150872 KB Output is correct
11 Correct 25 ms 187972 KB Output is correct
12 Correct 25 ms 234332 KB Output is correct
13 Correct 118 ms 167244 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 3 ms 29276 KB Output is correct
3 Correct 7 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 5 ms 49756 KB Output is correct
7 Correct 8 ms 29528 KB Output is correct
8 Correct 20 ms 117596 KB Output is correct
9 Correct 17 ms 133980 KB Output is correct
10 Correct 19 ms 150872 KB Output is correct
11 Correct 25 ms 187972 KB Output is correct
12 Correct 25 ms 234332 KB Output is correct
13 Correct 118 ms 167244 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 4 ms 33884 KB Output is correct
16 Correct 7 ms 56924 KB Output is correct
17 Correct 7 ms 59224 KB Output is correct
18 Correct 14 ms 117596 KB Output is correct
19 Correct 119 ms 167264 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 3 ms 29276 KB Output is correct
3 Correct 7 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 5 ms 49756 KB Output is correct
7 Correct 8 ms 29528 KB Output is correct
8 Correct 20 ms 117596 KB Output is correct
9 Correct 17 ms 133980 KB Output is correct
10 Correct 19 ms 150872 KB Output is correct
11 Correct 25 ms 187972 KB Output is correct
12 Correct 25 ms 234332 KB Output is correct
13 Correct 118 ms 167244 KB Output is correct
14 Correct 1 ms 8796 KB Output is correct
15 Correct 4 ms 33884 KB Output is correct
16 Correct 7 ms 56924 KB Output is correct
17 Correct 7 ms 59224 KB Output is correct
18 Correct 14 ms 117596 KB Output is correct
19 Correct 119 ms 167264 KB Output is correct
20 Correct 24 ms 144732 KB Output is correct
21 Correct 10 ms 51404 KB Output is correct
22 Correct 14 ms 117340 KB Output is correct
23 Correct 9 ms 22520 KB Output is correct
24 Runtime error 38 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -