Submission #952678

#	Time	Username	Problem	Language	Result	Execution time	Memory
952678		Beerus13	Holding (COCI20_holding)	C++14	110 / 110	90 ms	14068 KiB

holding

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e2 + 5;

bool maximize(auto &a, auto b) {
    if(a >= b) return true;
    a = b;
    return false;
}

int n, a[N], k, l, r;
int pre[N][N * N], suf[N][N * N], tmp[N][N * N];

void solve() {
    cin >> n >> l >> r >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int j = 1; j < l; ++j) {
        swap(tmp, pre);
        memset(pre, 0, sizeof(pre));
        for(int i = l; i <= r; ++i) {
            for(int cost = 0; cost <= k; ++cost) {
                maximize(pre[i][cost], pre[i - 1][cost]);
                maximize(pre[i][cost], tmp[i][cost]);
                if(cost + i - j <= k) 
                    maximize(pre[i][cost + i - j], tmp[i - 1][cost] + a[i] - a[j]);
            }
        }
    }
    for(int j = n; j > r; --j) {
        swap(tmp, suf);
        memset(suf, 0, sizeof(suf));
        for(int i = r; i >= l; --i) {
            for(int cost = 0; cost <= k; ++cost) {
                maximize(suf[i][cost], suf[i + 1][cost]);
                maximize(suf[i][cost], tmp[i][cost]);
                if(cost - i + j <= k) 
                    maximize(suf[i][cost - i + j], tmp[i + 1][cost] + a[i] - a[j]);
            }
        }
    }
    int ans = 0, res = 0;
    res = max(pre[r][k], suf[l][k]);
    for(int i = l; i <= r; ++i) {
        for(int cost = 0; cost <= k; ++cost) {
            maximize(res, pre[i][cost] + suf[i + 1][k - cost]);
        }
    }
    for(int i = l; i <= r; ++i) ans += a[i];
    cout << ans - res << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message (stderr)

holding.cpp:7:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool maximize(auto &a, auto b) {
      |               ^~~~
holding.cpp:7:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    7 | bool maximize(auto &a, auto b) {
      |                        ^~~~

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