oj.uz

Submission #901280

# Submission time Handle Problem Language Result Execution time Memory
901280 2024-01-09T09:06:02 Z nguyen31hoang08minh2003 Holding (COCI20_holding) C++14
88 / 110
 126 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;

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];

    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 6 ms 31324 KB Output is correct
3 Correct 8 ms 53956 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45776 KB Output is correct
6 Correct 6 ms 49872 KB Output is correct
7 Correct 9 ms 33628 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 6 ms 31324 KB Output is correct
3 Correct 8 ms 53956 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45776 KB Output is correct
6 Correct 6 ms 49872 KB Output is correct
7 Correct 9 ms 33628 KB Output is correct
8 Correct 13 ms 94812 KB Output is correct
9 Correct 15 ms 109404 KB Output is correct
10 Correct 25 ms 150876 KB Output is correct
11 Correct 25 ms 175444 KB Output is correct
12 Correct 23 ms 197204 KB Output is correct
13 Correct 126 ms 169100 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 6 ms 31324 KB Output is correct
3 Correct 8 ms 53956 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45776 KB Output is correct
6 Correct 6 ms 49872 KB Output is correct
7 Correct 9 ms 33628 KB Output is correct
8 Correct 13 ms 94812 KB Output is correct
9 Correct 15 ms 109404 KB Output is correct
10 Correct 25 ms 150876 KB Output is correct
11 Correct 25 ms 175444 KB Output is correct
12 Correct 23 ms 197204 KB Output is correct
13 Correct 126 ms 169100 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 36056 KB Output is correct
16 Correct 6 ms 52824 KB Output is correct
17 Correct 7 ms 55132 KB Output is correct
18 Correct 13 ms 101212 KB Output is correct
19 Correct 125 ms 169304 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 6 ms 31324 KB Output is correct
3 Correct 8 ms 53956 KB Output is correct
4 Correct 5 ms 49756 KB Output is correct
5 Correct 5 ms 45776 KB Output is correct
6 Correct 6 ms 49872 KB Output is correct
7 Correct 9 ms 33628 KB Output is correct
8 Correct 13 ms 94812 KB Output is correct
9 Correct 15 ms 109404 KB Output is correct
10 Correct 25 ms 150876 KB Output is correct
11 Correct 25 ms 175444 KB Output is correct
12 Correct 23 ms 197204 KB Output is correct
13 Correct 126 ms 169100 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 36056 KB Output is correct
16 Correct 6 ms 52824 KB Output is correct
17 Correct 7 ms 55132 KB Output is correct
18 Correct 13 ms 101212 KB Output is correct
19 Correct 125 ms 169304 KB Output is correct
20 Correct 23 ms 132556 KB Output is correct
21 Correct 9 ms 51292 KB Output is correct
22 Correct 15 ms 121436 KB Output is correct
23 Correct 6 ms 22108 KB Output is correct
24 Runtime error 41 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -