Submission #53364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53364	2018-06-29T15:13:51 Z	MatheusLealV	K blocks (IZhO14_blocks)	C++17	53 / 100	1000 ms	95728 KB

blocks

#include <bits/stdc++.h>
#define N 100010
#define K 110
#define inf 200000000000000000LL
using namespace std;
typedef long long ll;

ll n, k, v[N], pref[N], dp[N][K], best[N][K];

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>k;

	for(int i = 1; i <= n; i++) cin>>v[i];

	for(int i = 0; i < N; i++)
		for(int j = 0; j < K; j++)
			dp[i][j] = inf;

	dp[0][1] = 0;

	for(int i = 1; i <= n; i++)
	{
		dp[i][1] = max(dp[i - 1][1], v[i]);

		best[i][1] = dp[i][1];

		pref[i] = pref[i - 1] + v[i];
	}

	dp[0][0] = 0;

	dp[0][1] = inf;

	for(int q = 2; q <= k; q++)
	{
		for(int i = 1; i <= n; i++)
		{
			ll maior = v[i];

			if(i < q) dp[i][q] = inf;

			if(i == q)
			{
				dp[i][q] = pref[i];

				best[i][q] = v[i];

				continue;
			}

			for(int j = i; j >= 1; j--)
			{
				maior = max(maior, v[j]);

				dp[i][q] = min(dp[i][q], dp[j - 1][q - 1] + maior);
			}
			/*if(i < q) dp[i][q] = inf;

			if(i == q)
			{
				dp[i][q] = pref[i];

				best[i][q] = v[i];

				continue;
			}

			ll A = dp[i - 1][q] + max(v[i] - best[i - 1][q], 0LL);

			ll B = dp[i - 1][q - 1] + v[i];

			if(A <= B) best[i][q] = max(v[i], best[i - 1][q]);

			else best[i][q] = v[i];

			dp[i][q] = min(A, B);*/
		}
	}

	cout<<dp[n][k]<<'\n';
}

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	86520 KB	Output is correct
2	Correct	59 ms	86520 KB	Output is correct
3	Correct	60 ms	86520 KB	Output is correct
4	Correct	60 ms	86572 KB	Output is correct
5	Correct	61 ms	86660 KB	Output is correct
6	Correct	66 ms	86664 KB	Output is correct
7	Correct	63 ms	86664 KB	Output is correct
8	Correct	65 ms	86668 KB	Output is correct
9	Correct	60 ms	86668 KB	Output is correct
10	Correct	60 ms	86680 KB	Output is correct
11	Correct	60 ms	86680 KB	Output is correct
12	Correct	60 ms	86680 KB	Output is correct
13	Correct	62 ms	86684 KB	Output is correct
14	Correct	62 ms	86736 KB	Output is correct
15	Correct	60 ms	86736 KB	Output is correct
16	Correct	67 ms	86736 KB	Output is correct
17	Correct	69 ms	86736 KB	Output is correct
18	Correct	69 ms	86836 KB	Output is correct

Subtask #2

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	86836 KB	Output is correct
2	Correct	60 ms	86836 KB	Output is correct
3	Correct	61 ms	86836 KB	Output is correct
4	Correct	60 ms	86836 KB	Output is correct
5	Correct	60 ms	86836 KB	Output is correct
6	Correct	69 ms	86836 KB	Output is correct
7	Correct	66 ms	86836 KB	Output is correct
8	Correct	69 ms	86836 KB	Output is correct
9	Correct	60 ms	86836 KB	Output is correct
10	Correct	60 ms	86836 KB	Output is correct
11	Correct	60 ms	86836 KB	Output is correct
12	Correct	63 ms	86836 KB	Output is correct
13	Correct	81 ms	86836 KB	Output is correct
14	Correct	61 ms	86836 KB	Output is correct
15	Correct	60 ms	86836 KB	Output is correct
16	Correct	59 ms	86836 KB	Output is correct
17	Correct	63 ms	86836 KB	Output is correct
18	Correct	61 ms	86836 KB	Output is correct
19	Correct	60 ms	86848 KB	Output is correct
20	Correct	59 ms	86852 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	86860 KB	Output is correct
2	Correct	60 ms	86988 KB	Output is correct
3	Correct	62 ms	86988 KB	Output is correct
4	Correct	60 ms	86988 KB	Output is correct
5	Correct	61 ms	86988 KB	Output is correct
6	Correct	60 ms	86988 KB	Output is correct
7	Correct	61 ms	86988 KB	Output is correct
8	Correct	63 ms	87096 KB	Output is correct
9	Correct	59 ms	87096 KB	Output is correct
10	Correct	61 ms	87096 KB	Output is correct
11	Correct	72 ms	87096 KB	Output is correct
12	Correct	68 ms	87096 KB	Output is correct
13	Correct	70 ms	87096 KB	Output is correct
14	Correct	69 ms	87096 KB	Output is correct
15	Correct	61 ms	87096 KB	Output is correct
16	Correct	66 ms	87128 KB	Output is correct
17	Correct	67 ms	87128 KB	Output is correct
18	Correct	73 ms	87208 KB	Output is correct
19	Correct	62 ms	87208 KB	Output is correct

Subtask #4

0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1093 ms	95728 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-