제출 #536679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536679		blue	K개의 묶음 (IZhO14_blocks)	C++17	100 / 100	337 ms	5640 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<ll> Aval;
		vector<ll> DPprev;
		vector<int> mxp;
		vector<ll> mndp{INF};

		// 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]));

			Aval.push_back(A[i]);
			DPprev.push_back(DP[k-1][i-1]);
			// mxp
			mndp.push_back(min(mndp.back(), Aval.back() + DPprev.back()));

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

			ll mnright = +INF;

			while(A[mxp.back()] <= A[i])
			{
				mnright = min(mnright, DPprev.back());

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

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

			Aval[sz(Aval)-1] = A[i];
			DPprev[sz(DPprev)-1] = min(DPprev.back(), mnright);
			// DPpre
			mndp.pop_back();
			mndp.push_back(min(mndp.back(), Aval.back() + DPprev.back()));

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

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

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

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

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