Submission #53367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53367	2018-06-29T15:14:20 Z	MatheusLealV	K blocks (IZhO14_blocks)	C++17	53 / 100	1000 ms	95444 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];
			
			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	60 ms	86520 KB	Output is correct
2	Correct	61 ms	86744 KB	Output is correct
3	Correct	77 ms	86744 KB	Output is correct
4	Correct	70 ms	86744 KB	Output is correct
5	Correct	66 ms	86752 KB	Output is correct
6	Correct	66 ms	86776 KB	Output is correct
7	Correct	60 ms	86776 KB	Output is correct
8	Correct	69 ms	86776 KB	Output is correct
9	Correct	60 ms	86776 KB	Output is correct
10	Correct	61 ms	86776 KB	Output is correct
11	Correct	64 ms	86776 KB	Output is correct
12	Correct	61 ms	86776 KB	Output is correct
13	Correct	60 ms	86808 KB	Output is correct
14	Correct	60 ms	86808 KB	Output is correct
15	Correct	70 ms	86808 KB	Output is correct
16	Correct	63 ms	86808 KB	Output is correct
17	Correct	70 ms	86908 KB	Output is correct
18	Correct	60 ms	86908 KB	Output is correct

Subtask #2

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	86908 KB	Output is correct
2	Correct	61 ms	86908 KB	Output is correct
3	Correct	60 ms	86908 KB	Output is correct
4	Correct	61 ms	86908 KB	Output is correct
5	Correct	60 ms	86908 KB	Output is correct
6	Correct	60 ms	86908 KB	Output is correct
7	Correct	60 ms	86908 KB	Output is correct
8	Correct	60 ms	86908 KB	Output is correct
9	Correct	59 ms	86908 KB	Output is correct
10	Correct	60 ms	86908 KB	Output is correct
11	Correct	60 ms	86908 KB	Output is correct
12	Correct	62 ms	86908 KB	Output is correct
13	Correct	61 ms	86908 KB	Output is correct
14	Correct	60 ms	86908 KB	Output is correct
15	Correct	75 ms	86908 KB	Output is correct
16	Correct	59 ms	86908 KB	Output is correct
17	Correct	59 ms	86908 KB	Output is correct
18	Correct	61 ms	86908 KB	Output is correct
19	Correct	67 ms	86908 KB	Output is correct
20	Correct	66 ms	86908 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	86908 KB	Output is correct
2	Correct	63 ms	86908 KB	Output is correct
3	Correct	69 ms	86908 KB	Output is correct
4	Correct	61 ms	86908 KB	Output is correct
5	Correct	63 ms	86908 KB	Output is correct
6	Correct	61 ms	86908 KB	Output is correct
7	Correct	61 ms	86908 KB	Output is correct
8	Correct	61 ms	86908 KB	Output is correct
9	Correct	60 ms	86908 KB	Output is correct
10	Correct	68 ms	86908 KB	Output is correct
11	Correct	59 ms	86908 KB	Output is correct
12	Correct	60 ms	86908 KB	Output is correct
13	Correct	60 ms	86908 KB	Output is correct
14	Correct	59 ms	86908 KB	Output is correct
15	Correct	62 ms	86908 KB	Output is correct
16	Correct	71 ms	86908 KB	Output is correct
17	Correct	61 ms	86908 KB	Output is correct
18	Correct	61 ms	86908 KB	Output is correct
19	Correct	60 ms	86908 KB	Output is correct

Subtask #4

0 / 47.0

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