Submission #672930

#	Time	Username	Problem	Language	Result	Execution time	Memory
672930		viwlesxq	K개의 묶음 (IZhO14_blocks)	C++17	100 / 100	285 ms	84312 KiB

blocks

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef string str;

#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

const int inf = 1e9 + 7;
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	int a[n+1];
	for (int i = 1; i <= n; i++) cin >> a[i];
	vector <vector <ll>> dp(n + 1, vector <ll> (k + 1, inf));
	dp[0][0] = 0;
	int mx = 0;
	for (int i = 1; i <= n; i++) {
		mx = max(mx, a[i]);
		dp[i][1] = mx;
	}
	for (int j = 2; j <= k; j++) {
		stack <pair <int, ll>> stk;
		for (int i = j - 1; i <= n; i++) {
			ll last = dp[i-1][j-1];
			while (!stk.empty() && stk.top().F < a[i]) {
				last = min(last, stk.top().S);
				stk.pop();
			}
			if (stk.empty() || stk.top().S + stk.top().F > a[i] + last) stk.push({a[i], last});
			if (i >= j) dp[i][j] = stk.top().F + stk.top().S; 
		}
	}
	cout << dp[n][k];
}

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