oj.uz

Submission #882263

# Submission time Handle Problem Language Result Execution time Memory
882263 2023-12-02T21:08:39 Z OAleksa K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 4444 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -