제출 #1199592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199592		A_M_Namdar	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	611 ms	53096 KiB

blocks

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("tune=native")
using namespace std;

const int N = 1e5 + 10, M = 100 + 10, inf = 1e9 + 10, LG = 20;
int n, k, a[N], dp[N][M], dp2[N], mini[N][20], lg[N];

int get_min(int l, int r) {
	l = max(l, 0), r = min(r, n);
	if (l == r) 
		return inf;
//	cout << l << "       " << r << '\n';
	return min(mini[l][lg[r - l]], mini[r - (1 << lg[r - l])][lg[r - l]]);
}

void input() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) 
		cin >> a[i];
}

void solve() {
	for (int i = 2; i < N; i++) 
		lg[i] = lg[i >> 1] + 1;
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		dp2[i] = i - 1;
		while (dp2[i] > -1 && a[dp2[i]] <= a[i]) 
			dp2[i] = dp2[dp2[i]];
		if (a[i] > tmp)
			tmp = a[i];
		dp[i][1] = tmp;
	}
	for (int j = 2; j <= k; j++) {
		for (int i = 0; i < n; i++) 
			mini[i][0] = dp[i][j - 1];
		for (int e = 1; e < LG; e++) 
			for (int i = 0; i + (1 << e) <= n; i++) 
				mini[i][e] = min(mini[i][e - 1], mini[i + (1 << (e - 1))][e - 1]);
		vector<int> vec, vec2;
		vec.push_back(1e9 + 10);
		vec2.push_back(1e9 + 10);
		for (int i = 0; i < n; i++) {
			int p = i - 1;
			while (p > dp2[i]) {
				p = dp2[p];
				vec.pop_back();
				vec2.pop_back();
			}
			vec.push_back(get_min(dp2[i], i) + a[i]);
			vec2.push_back(min(vec2.back(), vec.back()));
			dp[i][j] = vec2.back();
//			for (int x: vec) 
//				cout << x << ' ';
//			cout << '\n';
//			cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		}
	}
	cout << dp[n - 1][k];
}

int main() {
//	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

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