Submission #200947

#	Time	Username	Problem	Language	Result	Execution time	Memory
200947		ZwariowanyMarcin	Holding (COCI20_holding)	C++14	110 / 110	290 ms	251000 KiB

holding

#include <bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define cat(x) cerr << #x << " = " << x << endl
#define ss(x) (int) x.size()

using namespace std;

const int nax = 102;

int n, L, R, k;
int a[nax];

int dp[nax][nax][10001];
int dp2[nax][nax][10001];

bool ok(int x, int y) {
	int r = 0;
	r += (L <= x && x <= R);
	r += (L <= y && y <= R);
	return (r == 1);
}

int main() {
	scanf ("%d%d%d%d", &n, &L, &R, &k);
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		scanf ("%d", a + i);
		if (L <= i && i <= R) sum += a[i];
	}
	
	for (int dl = 1; dl <= n; ++dl) {
		for (int l = 1; l + dl - 1 <= R; ++l) {
			int r = l + dl - 1;
			for (int cost = 0; cost <= k; ++cost) {
				dp[l][r][cost] = min(dp[l + 1][r][cost], dp[l][r - 1][cost]);
				if (abs(l - r) <= cost && ok(l, r)) {
					int x = 0;
					if (L <= l && l <= R) {
						x -= a[l];
						x += a[r];
					}
					else {
						x += a[l];
						x -= a[r];
					}
					dp[l][r][cost] = min(dp[l][r][cost], dp[l + 1][r - 1][cost - abs(l - r)] + x);
				}
			}
		}
	}
	
	for (int dl = 1; dl <= n; ++dl) {
		for (int l = L; l + dl - 1 <= n; ++l) {
			int r = l + dl - 1;
			for (int cost = 0; cost <= k; ++cost) {
				dp2[l][r][cost] = min(dp2[l + 1][r][cost], dp2[l][r - 1][cost]);
				if (abs(l - r) <= cost && ok(l, r)) {
					int x = 0;
					if (L <= l && l <= R) {
						x -= a[l];
						x += a[r];
					}
					else {
						x += a[l];
						x -= a[r];
					}
					dp2[l][r][cost] = min(dp2[l][r][cost], dp2[l + 1][r - 1][cost - abs(l - r)] + x);
				}
			}
		}
	}
	
	int g = 0;
	for (int i = L - 1; i <= R; ++i)
		for (int c = 0; c <= k; ++c)
			g = min(g, dp[1][i][c] + dp2[i + 1][n][k - c]);
	
	printf ("%d\n", sum + g);
	
	return 0;
}

Compilation message (stderr)

holding.cpp: In function 'int main()':
holding.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d%d", &n, &L, &R, &k);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", a + i);
   ~~~~~~^~~~~~~~~~~~~

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