oj.uz

Submission #957718

# Submission time Handle Problem Language Result Execution time Memory
957718 2024-04-04T08:44:41 Z vjudge1 Holding (COCI20_holding) C++17
110 / 110
 86 ms 58192 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

#define pb push_back
#define ll long long
#define i2 array<int, 2>
#define SZ(x) (int) (x).size()

const int N = 100 + 4, Max_K = N * (N - 1) / 2;

int n, l, r, k, a[N], dpL[N][N][Max_K], dpR[N][N][Max_K];

void solve() {
    cin >> n >> l >> r >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int L = l - 1; L >= 1; L--) {
        for (int R = l; R <= r; R++) {
            for (int K = 0; K <= k; K++) {
                dpL[L][R][K] = min({0, dpL[L + 1][R][K], dpL[L][R - 1][K], dpL[L + 1][R - 1][K]});
                int cost = R - L;
                if (cost <= K)
                    dpL[L][R][K] = min(dpL[L][R][K], dpL[L + 1][R - 1][K - cost] + a[L] - a[R]);
            }
        }
    }
    for (int L = r; L >= l; L--) {
        for (int R = r + 1; R <= n; R++) {
            for (int K = 0; K <= k; K++) {
                dpR[L][R][K] = min({0, dpR[L + 1][R][K], dpR[L][R - 1][K], dpR[L + 1][R - 1][K]});
                int cost = R - L;
                if (cost <= K)
                    dpR[L][R][K] = min(dpR[L][R][K], dpR[L + 1][R - 1][K - cost] - a[L] + a[R]);
            }
        }
    }

    int ans = 0;
    for (int i = l - 1; i <= r; i++) 
        for (int j = 0; j <= k; j++) 
            ans = min(ans, dpL[1][i][j] + dpR[i + 1][n][k - j]);
    debug(ans);
    for (int i = l; i <= r; i++)
        ans += a[i];
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Compilation message

holding.cpp: In function 'void solve()':
holding.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
holding.cpp:49:5: note: in expansion of macro 'debug'
   49 |     debug(ans);
      |     ^~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 2 ms 6864 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 23 ms 17320 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 2 ms 6864 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 23 ms 17320 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 1 ms 3676 KB Output is correct
17 Correct 3 ms 8028 KB Output is correct
18 Correct 3 ms 7004 KB Output is correct
19 Correct 24 ms 17248 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 2 ms 6864 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 23 ms 17320 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 1 ms 3676 KB Output is correct
17 Correct 3 ms 8028 KB Output is correct
18 Correct 3 ms 7004 KB Output is correct
19 Correct 24 ms 17248 KB Output is correct
20 Correct 6 ms 18776 KB Output is correct
21 Correct 4 ms 11224 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 6 ms 16476 KB Output is correct
24 Correct 8 ms 15704 KB Output is correct
25 Correct 86 ms 58192 KB Output is correct