Submission #1123720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123720		mingga	Holding (COCI20_holding)	C++20	110 / 110	57 ms	12360 KiB

holding

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int MOD = 1e9 + 7;
const int inf = 2e18;
const int N = 105;
const int K = 1e4 + 5;
int n, L, R, k, a[N];
int lef[N][K], rig[N][K], nxt[N][K];
int S;

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	cin >> n >> L >> R >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int t = 0; t <= k; t++) {
		for(int j = L; j <= R; j++) {
			lef[j][t] = lef[j - 1][t] + a[j];
		}
		for(int j = R; j >= L; j--) {
			rig[j][t] = rig[j + 1][t] + a[j];
		}
	}
	for(int i = 1; i < L; i++) {
		for(int j = L; j <= R; j++) {
			for(int t = 0; t <= k; t++) {
				nxt[j][t] = min(nxt[j - 1][t] + a[j], lef[j][t]);
				int cost = abs(i - j);
				if(t >= cost) {
					nxt[j][t] = min(nxt[j][t], lef[j - 1][t - cost] + a[i]);
				}
			}	
		}
		for(int j = L; j <= R; j++) {
			for(int t = 0; t <= k; t++) {
				lef[j][t] = nxt[j][t];
			}	
		}
	}
	for(int i = n; i > R; i--) {
		for(int j = R; j >= L; j--) {
			for(int t = 0; t <= k; t++) {
				nxt[j][t] = min(nxt[j + 1][t] + a[j], rig[j][t]);
				int cost = abs(i - j);
				if(t >= cost) {
					nxt[j][t] = min(nxt[j][t], rig[j + 1][t - cost] + a[i]);
				}
				// cout << i << ' ' << j << ' ' << t << ' ' << nxt[j][t] << ln;
			}	
		}
		for(int j = R; j >= L; j--) {
			for(int t = 0; t <= k; t++) {
				rig[j][t] = nxt[j][t];
			}	
		}
	}
	int ans = min(lef[R][k], rig[L][k]);
	for(int i = L; i < R; i++) {
		for(int t = 0; t <= k; t++) {
			// cout << i << ' ' << t << ' ' << lef[i][t] << ' ' << rig[i + 1][k - t] << ln;
			ans = min(ans, lef[i][t] +  rig[i + 1][k - t]);
		}
	}
	cout << ans;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

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