Submission #957760

#	Time	Username	Problem	Language	Result	Execution time	Memory
957760		ArashJafariyan	Holding (COCI20_holding)	C++17	110 / 110	85 ms	58216 KiB

holding

#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 (stderr)

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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22