oj.uz

Submission #200942

# Submission time Handle Problem Language Result Execution time Memory
200942 2020-02-08T18:24:03 Z ZwariowanyMarcin Holding (COCI20_holding) C++14
55 / 110
 59 ms 50680 KB 
#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 = 101;

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

int dp[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 <= n; ++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);
				}
			}
		}
	}
	
	printf ("%d\n", sum + dp[1][n][k]);
	
	return 0;
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:27: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:30: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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 8 ms 3448 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 8 ms 3448 KB Output is correct
8 Correct 7 ms 6008 KB Output is correct
9 Correct 8 ms 6136 KB Output is correct
10 Correct 8 ms 6140 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 8 ms 6264 KB Output is correct
13 Correct 59 ms 50680 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 8 ms 3448 KB Output is correct
8 Correct 7 ms 6008 KB Output is correct
9 Correct 8 ms 6136 KB Output is correct
10 Correct 8 ms 6140 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 8 ms 6264 KB Output is correct
13 Correct 59 ms 50680 KB Output is correct
14 Correct 7 ms 5752 KB Output is correct
15 Correct 8 ms 6136 KB Output is correct
16 Incorrect 8 ms 5880 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 8 ms 3448 KB Output is correct
8 Correct 7 ms 6008 KB Output is correct
9 Correct 8 ms 6136 KB Output is correct
10 Correct 8 ms 6140 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 8 ms 6264 KB Output is correct
13 Correct 59 ms 50680 KB Output is correct
14 Correct 7 ms 5752 KB Output is correct
15 Correct 8 ms 6136 KB Output is correct
16 Incorrect 8 ms 5880 KB Output isn't correct
17 Halted 0 ms 0 KB -