Submission #515798

#	Time	Username	Problem	Language	Result	Execution time	Memory
515798		thiago_bastos	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	316 KiB

blocks

#include "bits/stdc++.h"

using namespace std;
 
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const i64 INF = 1e15L;

void solve() {
	
	int n, k;

	cin >> n >> k;

	vector<int> a(n + 1);
	vector<i64> dp(n + 1, INF);

	a[0] = 1e9;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	
	dp[0] = 0;

	for(int i = 1; i <= k; ++i) {
		vector<int> c;
		vector<i64> cost, pre, val(n + 1, INF);
		
		c.push_back(0);
		cost.push_back(INF);
		cost.push_back(dp[0]);
		pre.push_back(dp[0]);

		for(int j = 1; j <= n; ++j) {
			i64 x = dp[j - 1];			
			while(!c.empty() && c.back() < a[j]) {
				x = min(x, cost.back());
				c.pop_back();
				pre.pop_back();
				cost.pop_back();
			}
			c.push_back(a[j]);
			pre.push_back(min(cost.back(), x + a[j]));
			cost.push_back(x);		
			val[j] = pre.back();	
		}

		swap(dp, val);
	}

	cout << dp.back() << '\n';
}
 
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

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