Submission #1089616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089616		xnqs	K blocks (IZhO14_blocks)	C++17	53 / 100	1047 ms	39584 KiB

blocks

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

const int BULAN = 3;
int x, p;
int arr[100005];
int sp_tb[17][100005];
int64_t dp[105][100005];

void build_sparse_table() {
	for (int l = 1; l < 17; l++) {
		for (int i = 1; i+(1<<l)-1 <= x; i++) {
			sp_tb[l][i] = std::max(sp_tb[l-1][i], sp_tb[l-1][i+(1<<(l-1))]);
		}
	}
}

inline int max_query(int l, int r) {
	int lvl = 31-__builtin_clz(r-l+1);
	return std::max(sp_tb[lvl][l], sp_tb[lvl][r-(1<<lvl)+1]);
}

void calculate_dp() {
	if (1LL*x*p*p<=1'000'000) {
		dp[1][0] = 0x3f3f3f3f3f3f3f3f;
		for (int i = 1; i <= x; i++) {
			dp[1][i] = max_query(1,i);
		}
	 
		for (int k = 2; k <= p; k++) {
			for (int i = 0; i < k; i++) {
				dp[k][i] = 0x3f3f3f3f3f3f3f3f;
			}
			for (int i = k; i <= x; i++) {
				dp[k][i] = 0x3f3f3f3f3f3f3f3f;
				for (int j = k; j <= i; j++) {
					dp[k][i] = std::min(dp[k][i], dp[k-1][j-1] + max_query(j,i));
				}
			}
		}
		return;
	}

	dp[1][0] = 0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i <= x; i++) {
		dp[1][i] = max_query(1,i);
	}

	for (int k = 2; k <= p; k++) {
		std::priority_queue<std::pair<int64_t,int>, std::vector<std::pair<int64_t,int>>, std::greater<std::pair<int64_t,int>>> pq;
		for (int i = 0; i < k; i++) {
			dp[k][i] = 0x3f3f3f3f3f3f3f3f;
			pq.emplace(dp[k-1][i],i+1);
		}
		for (int i = k; i <= x; i++) {
			dp[k][i] = 0x3f3f3f3f3f3f3f3f;
			std::vector<std::pair<int64_t,int>> tmp;
			for (int rep = 0; rep < BULAN && !pq.empty(); rep++) {
				auto [opt_dp, idx] = pq.top();
				dp[k][i] = std::min(dp[k][i], opt_dp + max_query(idx,i));
				tmp.emplace_back(opt_dp,idx);
				pq.pop();
			}
			while (!tmp.empty()) {
				pq.emplace(tmp.back());
				tmp.pop_back();
			}
			pq.emplace(dp[k-1][i],i+1);
		}
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> p;
	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		sp_tb[0][i] = arr[i];
	}

	build_sparse_table();
	calculate_dp();

	std::cout << dp[p][x] << "\n";
}

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