Submission #456225

#	Time	Username	Problem	Language	Result	Execution time	Memory
456225		grt	Holding (COCI20_holding)	C++17	110 / 110	127 ms	98516 KiB

holding

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 110, kax = 10000 + 10;
int n, l, r, k;
int val[nax];
int dp[nax][nax][kax];
int dp2[nax][nax][kax];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> l >> r >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> val[i];
	}
	for(int p1 = 1; p1 < l; p1++) {
		for(int p2 = l; p2 <= r; p2++) {
			for(int f = 0; f <= k; ++f) {
				dp[p1][p2][f] = min({dp[p1 - 1][p2][f], dp[p1][p2 - 1][f]});
				if(p2 - p1 <= f) {
					dp[p1][p2][f] = min(dp[p1][p2][f], dp[p1 - 1][p2 - 1][f - (p2 - p1)]  + val[p1] - val[p2]);
				}
			}
		}
	}
	for(int p1 = r + 1; p1 <= n; p1++) {
		for(int p2 = r; p2 >= l; p2--) {
			for(int f = 0; f <= k; ++f) {
				dp2[p1][p2][f] = min({dp2[p1 - 1][p2][f], dp2[p1][p2 + 1][f]});
				if(p1 - p2 <= f) {
					dp2[p1][p2][f] = min(dp2[p1][p2][f], dp2[p1 - 1][p2 + 1][f - (p1 - p2)] + val[p1] - val[p2]);
				}
			}
		}
	}
	int ans = 0;
	ans = min(ans, dp2[n][l][k]);
	for(int p = l; p <= r; ++p) {
		for(int k1 = 0; k1 <= k; ++k1) {
			ans = min(ans, dp[l - 1][p][k1] + dp2[n][p + 1][k - k1]);
		}
	}
	for(int i = l; i <= r; ++i) ans += val[i];
	cout << ans;
}

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