Submission #342738

#	Time	Username	Problem	Language	Result	Execution time	Memory
342738		maskoff	K blocks (IZhO14_blocks)	C++14	100 / 100	268 ms	42932 KiB

blocks

#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
 
const int N = 1e5 + 5;
 
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};
 
int n, k;
int dp[N][105], a[N];

int main() { 
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> k;
	memset(dp, 0x3f, sizeof(dp));
	int mx = 0;
	for (int i = 1; i <= n; i++) cin >> a[i], mx = max(mx, a[i]), dp[i][1] = mx;
	for (int block = 2; block <= k; block++) {
		stack<pii> s;
	 	for (int i = 1; i <= n; i++) {
	 		int opt = dp[i - 1][block - 1];
	 		while (!s.empty() && s.top().fr < a[i]) {
	 			opt = min(opt, s.top().sc);
	 			s.pop();
	 		}
	 		if (s.empty() || a[i] + opt < s.top().fr + s.top().sc) 
	 			s.push({a[i], opt});

	 		if (i >= block) dp[i][block] = s.top().fr + s.top().sc;
	 	}
	}
	cout << dp[n][k];
  return 0;
}  

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