Submission #1083705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083705		xnqs	K blocks (IZhO14_blocks)	C++17	53 / 100	1004 ms	1628 KiB

blocks

#pragma GCC optimize("Ofast")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
 
int x, k;
int arr[100005];
int dp[2][100005];
 
void divide(int l, int r, int optl, int optr, int idx) {
	if (l>r) {
		return;
	}
 
	int m = (l+r)>>1;
	int max = 0;
	int opt = -1;
	for (int i = std::min(m, optr+69); i >= std::max(1, optl-100); i--) {
		max = std::max(max, arr[i]);
		if (dp[idx][m] > dp[idx^1][i-1]+max) {
			dp[idx][m] = dp[idx^1][i-1]+max;
			opt = i;
		}
	}
 
	divide(l,m-1,optl,opt,idx);
	divide(m+1,r,opt,optr,idx);
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> x >> k;
	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
	}
 
	dp[1][0] = 0;
	for (int i = 1; i <= x; i++) {
		dp[1][i] = std::max(dp[1][i-1], arr[i]);
	}
	dp[1][0] = 0x3f3f3f3f;
	for (int i = 2; i <= k; i++) {
		for (int j = 0; j <= x; j++) {
			dp[i&1][j] = 0x3f3f3f3f;
		}
		divide(1,x,1,x,i&1);
	}
 
	std::cout << dp[k&1][x] << "\n";
}

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