Submission #1089632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089632		xnqs	K blocks (IZhO14_blocks)	C++17	53 / 100	1038 ms	1356 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 = 2;
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*p*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::pair<uint32_t,int> min1(0x3f3f3f3f,-1);
		std::pair<uint32_t,int> min2(0x3f3f3f3f,-1);
		for (int i = 0; i < k; i++) {
			dp[k][i] = 0x3f3f3f3f;
			if (dp[k-1][i]<=min1.first) {
				min2 = min1;
				min1.first = dp[k-1][i];
				min1.second = i+1;
			}
			else if (dp[k-1][i]<=min2.first) {
				min2.first = dp[k-1][i];
				min2.second = i+1;
			}
		}
		for (int i = k; i <= x; i++) {
			dp[k][i] = std::min(min1.first + max_query(min1.second, i), min2.first + max_query(min2.second, i));;
			if (dp[k-1][i]<=min1.first) {
				min2 = min1;
				min1.first = dp[k-1][i];
				min1.second = i+1;
			}
			else if (dp[k-1][i]<=min2.first) {
				min2.first = dp[k-1][i];
				min2.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