oj.uz

Submission #901319

# Submission time Handle Problem Language Result Execution time Memory
901319 2024-01-09T10:31:49 Z nguyen31hoang08minh2003 Holding (COCI20_holding) C++14
88 / 110
 411 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, INF = 0X3F3F3F3F;

int N, L, R, K, A[MAX_N];
bool visited[MAX_N][MAX_N][MAX_K];
signed result = INF, minimum[MAX_N][MAX_N][MAX_K], leftCost[MAX_N][MAX_K], rightCost[MAX_N][MAX_K];

long long findRightOptimalCost(const int i, const int j, const int 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) {
    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, k; i <= R; ++i)
        for (k = 0; k <= K; ++k)
            leftCost[i][k] = findLeftOptimalCost(i, L - 1, k);

    memset(visited, false, sizeof(visited));

    for (int i = L, k; i <= R; ++i)
        for (k = 0; k <= K; ++k)
            rightCost[i][k] = findRightOptimalCost(i, R + 1, 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 27 ms 123216 KB Output is correct
2 Correct 23 ms 141660 KB Output is correct
3 Correct 25 ms 167696 KB Output is correct
4 Correct 22 ms 164188 KB Output is correct
5 Correct 22 ms 160284 KB Output is correct
6 Correct 22 ms 164236 KB Output is correct
7 Correct 24 ms 141892 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 123216 KB Output is correct
2 Correct 23 ms 141660 KB Output is correct
3 Correct 25 ms 167696 KB Output is correct
4 Correct 22 ms 164188 KB Output is correct
5 Correct 22 ms 160284 KB Output is correct
6 Correct 22 ms 164236 KB Output is correct
7 Correct 24 ms 141892 KB Output is correct
8 Correct 24 ms 170312 KB Output is correct
9 Correct 30 ms 178768 KB Output is correct
10 Correct 31 ms 207452 KB Output is correct
11 Correct 34 ms 221776 KB Output is correct
12 Correct 45 ms 260812 KB Output is correct
13 Correct 153 ms 219792 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 123216 KB Output is correct
2 Correct 23 ms 141660 KB Output is correct
3 Correct 25 ms 167696 KB Output is correct
4 Correct 22 ms 164188 KB Output is correct
5 Correct 22 ms 160284 KB Output is correct
6 Correct 22 ms 164236 KB Output is correct
7 Correct 24 ms 141892 KB Output is correct
8 Correct 24 ms 170312 KB Output is correct
9 Correct 30 ms 178768 KB Output is correct
10 Correct 31 ms 207452 KB Output is correct
11 Correct 34 ms 221776 KB Output is correct
12 Correct 45 ms 260812 KB Output is correct
13 Correct 153 ms 219792 KB Output is correct
14 Correct 15 ms 117048 KB Output is correct
15 Correct 17 ms 129448 KB Output is correct
16 Correct 18 ms 135516 KB Output is correct
17 Correct 19 ms 133468 KB Output is correct
18 Correct 26 ms 166284 KB Output is correct
19 Correct 128 ms 219800 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 123216 KB Output is correct
2 Correct 23 ms 141660 KB Output is correct
3 Correct 25 ms 167696 KB Output is correct
4 Correct 22 ms 164188 KB Output is correct
5 Correct 22 ms 160284 KB Output is correct
6 Correct 22 ms 164236 KB Output is correct
7 Correct 24 ms 141892 KB Output is correct
8 Correct 24 ms 170312 KB Output is correct
9 Correct 30 ms 178768 KB Output is correct
10 Correct 31 ms 207452 KB Output is correct
11 Correct 34 ms 221776 KB Output is correct
12 Correct 45 ms 260812 KB Output is correct
13 Correct 153 ms 219792 KB Output is correct
14 Correct 15 ms 117048 KB Output is correct
15 Correct 17 ms 129448 KB Output is correct
16 Correct 18 ms 135516 KB Output is correct
17 Correct 19 ms 133468 KB Output is correct
18 Correct 26 ms 166284 KB Output is correct
19 Correct 128 ms 219800 KB Output is correct
20 Correct 29 ms 164180 KB Output is correct
21 Correct 24 ms 131676 KB Output is correct
22 Correct 23 ms 160088 KB Output is correct
23 Correct 25 ms 123228 KB Output is correct
24 Correct 60 ms 261344 KB Output is correct
25 Runtime error 411 ms 262144 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -