oj.uz

Submission #1093099

# Submission time Handle Problem Language Result Execution time Memory
1093099 2024-09-25T23:59:52 Z Hacv16 Holding (COCI20_holding) C++17
0 / 110
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -