Submission #1225577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225577		nhq0914	K blocks (IZhO14_blocks)	C++17	53 / 100	2 ms	328 KiB

blocks

#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a) (int)a.size()
#define ll long long
using namespace std;

int n, k, a[200001], dp[501], tdp[501];

stack <pair <int, int>> s;

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> k;
	F(i, 1, n) cin >> a[i];
	dp[0] = 0;
	F(i, 1, n) dp[i] = max(dp[i - 1], a[i]);
	F(j, 2, k) {
		while(N(s)) s.pop();
		memset(tdp, 63, sizeof tdp);
		F(i, j, n) {
			int min_f = dp[i - 1];
			while(N(s) && a[s.top().first] <= a[i]) {
				min_f = min(min_f, s.top().second);
				s.pop();
			}
			tdp[i] = min(tdp[N(s) ? s.top().first : 0], min_f + a[i]);
			s.push({i, min_f});
		}
		swap(tdp, dp);
	}
	cout << dp[n];
	return 0;
}

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