Submission #1124225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124225		Chinguun	K blocks (IZhO14_blocks)	C++20	100 / 100	105 ms	2952 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 6;
const ll INF = 1e15;

ll Old[N], New[N];
int a[N], sz;

pair<ll,ll> p[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
		Old[i] = max(Old[i - 1], (ll)a[i]);
	}
	for (int j = 2 ; j <= k ; ++ j) {
		sz = 0;
		for (int i = 1 ; i <= n ; ++ i) {
			ll Mn = j <= i ? Old[i - 1] : INF;
			while (sz && p[sz - 1].first <= a[i]) Mn = min(Mn, p[sz - 1].second), sz--;
			if (!sz || a[i] + Mn < p[sz - 1].first + p[sz - 1].second) sz++, p[sz - 1] = {a[i], Mn};
			New[i] = p[sz - 1].first + p[sz - 1].second;
		}
		swap(Old, New);
	}
	cout << Old[n];
}

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