Submission #1093099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093099		Hacv16	Holding (COCI20_holding)	C++17	0 / 110	1 ms	348 KiB

holding

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

#define int long long int
const int MAX = 115;
const int INF = 1e18 + 10;

int n, l, r, k, a[MAX];

int32_t main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> l >> r >> k;

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    vector<vector<vector<int>>> dpL(l + 1, vector<vector<int>>(n + 1, vector<int>(k + 1, INF)));
    dpL[0][0][0] = 0;

    for(int i = 1; i <= l; i++)
        for(int j = 0; j <= l; j++)
            for(int t = 0; t <= k; t++)
                dpL[i][j][t] = min(dpL[i - 1][j][t], (t >= i && j >= 1 ? dpL[i - 1][j - 1][t - i] + a[i] : INF));

    vector<vector<vector<int>>> dpR(n + 10, vector<vector<int>>(n + 1, vector<int>(k + 1, -INF)));
    dpR[n + 1][0][0] = 0;

    for(int i = n; i >= l; i--)
        for(int j = 0; j <= n; j++)
            for(int t = 0; t <= k; t++)
                dpR[i][j][t] = max(dpR[i + 1][j][t], (t >= i && j >= 1 ? dpR[i + 1][j - 1][t - i] + a[i] : -INF));

    int ans = INF;

    int sum = 0;
    for(int i = l; i <= r; i++) sum += a[i];

    for(int q = 0; q <= l; q++)
        for(int c = 0; c <= k; c++)
            for(int j = 0; j <= c; j++)
                ans = min(ans, sum + dpL[l - 1][q][c] - dpR[l][q][c - j]);

    cout << ans << '\n';
}

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