Submission #1089673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089673		xnqs	K blocks (IZhO14_blocks)	C++17	53 / 100	1067 ms	44164 KiB

blocks

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdint>
 
const int BULAN = 30;
int x, p;
int arr[100005];
int sp_tb[17][100005];
uint32_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*x*p<=50'000'000) {
		dp[1][0] = 0x3f3f3f3f;
		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] = 0x3f3f3f3f;
			}
			for (int i = k; i <= x; i++) {
				dp[k][i] = 0x3f3f3f3f;
				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] = 0x3f3f3f3f;
	for (int i = 1; i <= x; i++) {
		dp[1][i] = max_query(1,i);
	}
 
	for (int k = 2; k <= p; k++) {
		std::vector<std::pair<uint32_t,int>> min(BULAN,std::pair<uint32_t,int>(0x3f3f3f3f,0));
		for (int i = 0; i < k; i++) {
			dp[k][i] = 0x3f3f3f3f;

			int pos = -1;
			for (int j = 0; j < BULAN; j++) {
				if (min[j].first>dp[k-1][i]||(min[j].first==dp[k-1][i]&&min[j].second<i+1)) {
					pos = j;
					break;
				}
			}
			if (pos!=-1) {
				for (int j = BULAN-1; j > pos; j--){ 
					min[j] = min[j-1];
				}
				min[pos].first = dp[k-1][i];
				min[pos].second = i+1;
			}
		}
		for (int i = k; i <= x; i++) {
			dp[k][i] = 0x3f3f3f3f;
			for (int j = 0; j < BULAN; j++) {
				dp[k][i] = std::min(dp[k][i], min[j].first + max_query(min[j].second,i));
			}

			int pos = -1;
			for (int j = 0; j < BULAN; j++) {
				if (min[j].first>dp[k-1][i]||(min[j].first==dp[k-1][i]&&min[j].second<i+1)) {
					pos = j;
					break;
				}
			}
			if (pos!=-1) {
				for (int j = BULAN-1; j > pos; j--){ 
					min[j] = min[j-1];
				}
				min[pos].first = dp[k-1][i];
				min[pos].second = 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