제출 #250413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250413		srvlt	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	147 ms	2676 KiB

blocks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 100003, k0 = 101;
int n, k, a[n0], dp[2][n0];

struct T {
	int x, y, mn;
	void merge(const T & t) {
		if (t.x <= x) x = t.x;
		mn = min(mn, x + y);
	}
};
stack <T> st;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[1][i] = max(dp[1][i - 1], a[i]);
	}
	T cur;
	for (int i = 2; i <= k; i++) {
		while (!st.empty()) st.pop();
		for (int j = i; j <= n; j++) {
			cur.x = dp[(i & 1) ^ 1][j - 1], cur.y = a[j];
			cur.mn = cur.x + cur.y;
			while (!st.empty() && st.top().y <= cur.y) {
				cur.merge(st.top());
				st.pop();
			}
			if (!st.empty()) {
				cur.mn = min(cur.mn, st.top().mn);
			}
			st.push(cur);
			dp[i & 1][j] = cur.mn;
		}
	}
	cout << dp[k & 1][n];
}

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