oj.uz

Submission #206538

# Submission time Handle Problem Language Result Execution time Memory
206538 2020-03-03T19:28:21 Z luciocf Holding (COCI20_holding) C++14
110 / 110
 31 ms 25212 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;
const int maxk = 2505;
const int inf = 1e9+10;

int a[maxn];
int dp1[maxn][maxn][maxk], dp2[maxn][maxn][maxk];

int main(void)
{
	int n, l, r, k;
	scanf("%d %d %d %d", &n, &l, &r, &k);
	k = min(k, maxk-1);

	int soma = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);

		if (i >= l && i <= r)
			soma += a[i];
	}

	for (int i = 1; i < l; i++)
	{
		for (int j = l; j <= r; j++)
		{
			for (int x = 0; x <= k; x++)
			{
				dp1[i][j][x] = max(dp1[i][j-1][x], dp1[i-1][j][x]);

				if (x >= j-i)
					dp1[i][j][x] = max(dp1[i][j][x], a[j] - a[i] + dp1[i-1][j-1][x-(j-i)]);
			}
		}
	}

	for (int i = r; i >= l; i--)
	{
		for (int j = n; j > r; j--)
		{
			for (int x = 0; x <= k; x++)
			{
				dp2[i][j][x] = max(dp2[i+1][j][x], dp2[i][j+1][x]);

				if (x >= j-i)
					dp2[i][j][x] = max(dp2[i][j][x], a[i] - a[j] + dp2[i+1][j+1][x-(j-i)]);
			}
		}
	}

	int ans = 0;

	for (int x = 0; x <= k; x++)
		ans = max(ans, dp1[l-1][r][x]);
	for (int x = 0; x <= k; x++)
		ans = max(ans, dp2[l][r+1][x]);

	for (int i = l; i <= r; i++)
		for (int x = 0; x <= k; x++)
			ans = max(ans, dp1[l-1][i][x] + dp2[i+1][r+1][k-x]);

	printf("%d\n", soma-ans);
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:15:7: 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:21:8: 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 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 760 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 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 6 ms 2552 KB Output is correct
9 Correct 7 ms 2808 KB Output is correct
10 Correct 6 ms 3192 KB Output is correct
11 Correct 6 ms 3320 KB Output is correct
12 Correct 6 ms 2040 KB Output is correct
13 Correct 11 ms 6648 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 6 ms 2552 KB Output is correct
9 Correct 7 ms 2808 KB Output is correct
10 Correct 6 ms 3192 KB Output is correct
11 Correct 6 ms 3320 KB Output is correct
12 Correct 6 ms 2040 KB Output is correct
13 Correct 11 ms 6648 KB Output is correct
14 Correct 5 ms 632 KB Output is correct
15 Correct 5 ms 1144 KB Output is correct
16 Correct 6 ms 1660 KB Output is correct
17 Correct 6 ms 1784 KB Output is correct
18 Correct 6 ms 2936 KB Output is correct
19 Correct 11 ms 6648 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 6 ms 2552 KB Output is correct
9 Correct 7 ms 2808 KB Output is correct
10 Correct 6 ms 3192 KB Output is correct
11 Correct 6 ms 3320 KB Output is correct
12 Correct 6 ms 2040 KB Output is correct
13 Correct 11 ms 6648 KB Output is correct
14 Correct 5 ms 632 KB Output is correct
15 Correct 5 ms 1144 KB Output is correct
16 Correct 6 ms 1660 KB Output is correct
17 Correct 6 ms 1784 KB Output is correct
18 Correct 6 ms 2936 KB Output is correct
19 Correct 11 ms 6648 KB Output is correct
20 Correct 9 ms 6392 KB Output is correct
21 Correct 6 ms 2936 KB Output is correct
22 Correct 7 ms 4344 KB Output is correct
23 Correct 7 ms 2808 KB Output is correct
24 Correct 12 ms 12152 KB Output is correct
25 Correct 31 ms 25212 KB Output is correct