Submission #253399

#	Time	Username	Problem	Language	Result	Execution time	Memory
253399		vovamr	K blocks (IZhO14_blocks)	C++14	100 / 100	372 ms	84600 KiB

blocks

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x)              (x).begin(), (x).end()
#define inf                 1e18

using namespace std;

void solve() {
	int n, k;
	cin >> n >> k;
	vector <ll> v(n);
	for (auto &i : v) cin >> i;

	vector < vector <ll> > dp(n + 1, vector <ll> (k + 1));
	for (int i = 1; i <= n; ++i) dp[i][0] = inf;

	stack < pair <ll, ll> > st;
	for (int i = 1; i <= k; ++i) {
		while (!st.empty()) st.pop();
		dp[i][i] = dp[i - 1][i - 1] + v[i - 1]; st.push({v[i - 1], dp[i - 1][i - 1]});
		
		for (int j = i + 1; j <= n; ++j) {
			ll c = dp[j - 1][i - 1];
			while (!st.empty() && st.top().fi <= v[j - 1]) {
				c = min(c, st.top().se);
				st.pop();
			}
			if (st.empty() || st.top().fi + st.top().se > v[j - 1] + c) st.push({v[j - 1], c});
			dp[j][i] = st.top().fi + st.top().se;
		}
	}
	cout << dp[n][k];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	ifstream cin("input.txt");
//	ofstream cout("output.txt");
	int q = 1; // cin >> q;
	while (q--) solve();
}

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