Submission #536677

#	Time	Username	Problem	Language	Result	Execution time	Memory
536677		blue	K blocks (IZhO14_blocks)	C++17	53 / 100	1082 ms	596 KiB

blocks

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000LL;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	vll A(1+N, INF);
	for(int i = 1; i <= N; i++) cin >> A[i];

	ll* DP[1+K];
	DP[0] = new ll[1+N];
	DP[1] = new ll[1+N];
	for(int k = 2; k <= K; k++)
	{
		DP[k] = DP[k-2];
	}

	for(int i = 1; i <= N; i++)
	{
		DP[0][i] = DP[1][i] = +INF;
	}

	DP[0][0] = 0;

	for(int k = 1; k <= K; k++)
	{
		for(int i = 0; i < k; i++)
			DP[k][i] = +INF;

		for(int i = k; i <= N; i++)
		{
			DP[k][i] = +INF;

			for(int i2 = k-1; i2 <= i-1; i2++)
			{
				ll mxv = 0;
				for(int f = i2+1; f <= i; f++)
					mxv = max(mxv, A[f]);

				DP[k][i] = min(DP[k][i], mxv + DP[k-1][i2]);
			}
		}
	}

	cout << DP[K][N] << '\n';
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47