Submission #533845

#	Time	Username	Problem	Language	Result	Execution time	Memory
533845		sidon	K blocks (IZhO14_blocks)	C++17	100 / 100	65 ms	80824 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define minim(X, Y) (X = min(X, Y))

const int INF = 2e9;

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

	int N, K;
	cin >> N >> K;
	int A[N+1] {INF};

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

	int dp[N+1][K+1], dpMin[N+1][K+1];

	fill(dp[0], dp[0] + K + 1, INF);
	fill(dpMin[0], dpMin[0] + K + 1, INF);

	dp[0][0] = 0;

	vector<int> s {0};

	for(int i = 1; i <= N; ++i) {
		copy(dp[i-1], dp[i-1] + K + 1, dpMin[i]);

		while(A[s.back()] <= A[i]) {
			int j = s.back();
			s.pop_back();
			for(int k = 0; k <= K; ++k)
				minim(dpMin[i][k], dpMin[j][k]);
		}

		copy(dp[s.back()], dp[s.back()] + K + 1, dp[i]);
		dp[i][0] = INF;

		for(int k = 1; k <= K; ++k)
			minim(dp[i][k], A[i] + dpMin[i][k - 1]);

		s.push_back(i);
	}

	cout << dp[N][K];
}

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