Submission #882263

#	Time	Username	Problem	Language	Result	Execution time	Memory
882263		OAleksa	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	4444 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int maxn = 1e5 + 69;
const int inf = 1e9;
int st[4 * maxn], n, k, a[maxn], dp1[maxn], d[maxn], dp2[maxn];
void upd(int v, int tl, int tr, int p, int x) {
	if (tl == tr)
		st[v] = x;
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			upd(v * 2, tl, mid, p, x);
		else
			upd(v * 2 + 1, mid + 1, tr, p, x);
		st[v] = min(st[v * 2], st[v * 2 + 1]);
	}
}
int qry(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 1e9;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return min(qry(v * 2, tl, mid, l, r), qry(v * 2 + 1, mid + 1, tr, l, r));
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
   	cin >> n >> k;
   	for (int i = 1;i <= n;i++)
   		cin >> a[i];
   	
   	vector<int> st;
   	for (int i = 1;i <= n;i++) {
			while (!st.empty() && a[st.back()] < a[i]) 
				st.pop_back();
			if (!st.empty())
				d[i] = st.back();
			st.push_back(i);
   	}
   	dp1[0] = inf;
   	for (int j = 1;j <= k;j++) {
   		for (int i = 1;i <= n;i++)
   			upd(1, 1, n, i, dp1[i]);
   		for (int i = 0;i <= n;i++) {
   			if (j > i)
   				dp2[i] = inf;
   			else 
   				dp2[i] = min(dp1[d[i]], qry(1, 1, n, d[i] + 1, i) + a[i]);
   		}
   		for (int i = 0;i <= n;i++)
   			dp1[i] = dp2[i];
   	}
   	cout << dp1[n];
	}
	return 0;
}

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