Submission #159573

#	Time	Username	Problem	Language	Result	Execution time	Memory
159573		DrSwad	K blocks (IZhO14_blocks)	C++17	53 / 100	1095 ms	209776 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int K = 105;
const int INF = 1e9;

template <typename T>
class segmentTree {
	int n;
	vector<T> a;
	vector<T> st;
	T (*merge)(T, T);
	void build(int stI, int L, int R) {
		if (L == R) {
			st[stI] = a[L];
			return;
		}

		int mid = (L + R) / 2;
		build((stI << 1), L, mid);
		build((stI << 1) + 1, mid + 1, R);

		st[stI] = merge(st[(stI << 1)], st[(stI << 1) + 1]);
	}
	void update(int stI, int L, int R, int at, T val) {
		if (L == R) {
			st[stI] = val;
			return;
		}

		int mid = (L + R) / 2;
		if (at <= mid) update((stI << 1), L, mid, at, val);
		else update((stI << 1) + 1, mid + 1, R, at, val);

		st[stI] = merge(st[(stI << 1)], st[(stI << 1) + 1]);
	}
	T query(int stI, int L, int R, int l, int r) {
		if (l <= L && R <= r) return st[stI];

		int mid = (L + R) / 2;
		if (r <= mid) return query((stI << 1), L, mid, l, r);
		if (mid + 1 <= l) return query((stI << 1) + 1, mid + 1, R, l, r);

		return merge(
				query((stI << 1), L, mid, l, mid),
				query((stI << 1) + 1, mid + 1, R, mid + 1, r)
			);
	}
public:
	segmentTree(vector<T> _a, T (*_merge)(T, T)) {
		n = _a.size();
		a = _a;
		st.resize(4 * n + 1);
		merge = _merge;
		build(1, 0, n - 1);
	}
	T query(int l, int r) { // range [l, r], 0-based index
		return query(1, 0, n - 1, l, r);
	}
	void update(int at, T val) { // at is 0-based index
		update(1, 0, n - 1, at, val);
	}
};

int n, k;
int a[N];
int l[N];
int dp[K][N];
segmentTree<int>* st;

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif

	cin >> n >> k;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

	for (int i = 1; i <= n; i++) {
		int at = i - 1;
		while (at > 0 && a[at] < a[i]) at = l[at];
		l[i] = at;
	}

	fill(&dp[0][0], &dp[K][0], INF);
	dp[0][0] = 0;
	st = new segmentTree<int>(vector<int>(&dp[0][0], &dp[0][n + 1]), [](int i, int j) {return min(i, j);});

	for (int _k = 1; _k <= k; _k++) {
		for (int i = _k; i <= n; i++) {
			dp[_k][i] = min(a[i] + st->query(l[i], i - 1), dp[_k][l[i]]);
		}
		st = new segmentTree<int>(vector<int>(&dp[_k][0], &dp[_k][n + 1]), [](int i, int j) {return min(i, j);});
	}

	cout << dp[k][n] << endl;

	return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:80:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                               ~~~~~^~~~~~~~~~~~~

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