Submission #1124023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124023		ndquang	Holding (COCI20_holding)	C++20	88 / 110	212 ms	327680 KiB

holding

#include <bits/stdc++.h>
using namespace std;

/** Author: Nguyen Duy Quang **/

#define test int T; cin >> T; while(T--)
#define all(x) (x).begin(), (x).end()
#define Bit(x, y) ((x >> y) & 1)
#define int long long
#define pb push_back
#define fi first
#define sc second
#define inpFile(Task) freopen(Task".inp", "r", stdin);
#define outFile(Task) freopen(Task".out", "w", stdout);
#define submitFile(Task) inpFile(Task); outFile(Task);

using pii = pair<int, int>;
using ull = unsigned long long;
const int INF = (int)1e18, MOD1 = (int)1e9 + 7, MOD2 = (int)998244353;
template<class X, class Y> void maximize(X &a, const Y &b) { a = (a < b) ? b : a; }
template<class X, class Y> void minimize(X &a, const Y &b) { a = (a > b) ? b : a; }
template<class T> void add(T& a, T b) { a += b; if(a >= MOD1) a -= MOD1; }
template<class T> void sub(T& a, T b) { a -= b; if(a <= 0) a += MOD1; }

///END OF TEMPLATE

const int maxk = (int)1e4 + 8;

int n, l, r, k, a[108], dp[108][88][maxk];

signed main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    cin >> n >> l >> r >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int m = r - l + 1;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int x = 0; x <= k; x++) dp[i][j][x] = INF;
    for(int i = 0; i <= n; i++)
        for(int x = 0; x <= k; x++) dp[i][0][x] = 0;
    int res = INF;
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        for(int x = 0; x <= k; x++) {
            dp[i][j][x] = dp[i - 1][j][x];
            if(x >= abs(i - (l + j - 1))) minimize(dp[i][j][x], dp[i - 1][j - 1][x - abs(i - (l + j - 1))] + a[i]);
            if(j == m) minimize(res, dp[i][j][x]);
        }
    }
    cout << res;
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 0 / 22