Submission #536675

#	Time	Username	Problem	Language	Result	Execution time	Memory
536675		blue	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	324 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++)
	{
		// cerr << "\n\n\n\n\n k = " << k << '\n';
		vector<int> mxp;
		vector<ll> mndp;

		// DP[k][0] = 0;
		DP[k][0] = INF;

		for(int i = 1; i <= N; i++)
		{
			// cerr << "\n\n\n";
			// cerr << "i = " << i << '\n';
			// cerr << "push value " << k-1 << ' ' << i-1 << " : " << DP[k-1][i-1] << '\n';

			mxp.push_back(i-1);

			if(mndp.empty())
				mndp.push_back(DP[k-1][max(i-1, k-1)] + A[i]);
			else
				mndp.push_back(min(mndp.back(), DP[k-1][max(i-1, k-1)] + A[i]));

			// cerr << "push P " << mndp.back() << '\n';

			while(A[mxp.back()] <= A[i])
			{

				// cerr << "pop A " << mndp.back() << '\n';


				mxp.pop_back();
				mndp.pop_back();
			}

			// cerr << "pop B " << mndp.back() << '\n';

			mndp.pop_back();

			if(mndp.empty())
				mndp.push_back(DP[k-1][max(mxp.back(), k-1)] + A[i]);
			else
				mndp.push_back(min(mndp.back(), DP[k-1][max(mxp.back(), k-1)] + A[i]));

			// cerr << "push Q " << mndp.back() << '\n';

			DP[k][i] = mndp.back();

			// cerr << k << ' ' << i << " : " << DP[k][i] << '\n';
		}
	}

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

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