Submission #646296

#	Time	Username	Problem	Language	Result	Execution time	Memory
646296		ymm	K blocks (IZhO14_blocks)	C++17	100 / 100	601 ms	8076 KiB

blocks

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 131072;
const int K = 110;
const ll inf = 1e15;
ll dp[2][N];
ll a[N];
int n;

#pragma GCC optimize("O3,unroll-loops")
#define MIN(x, y) ((x)<(y)?(x):(y))

ll seg[2][2*N];
ll get(int k, int l, int r)
{
	l += N; r += N;
	ll ans = inf;
	while (l < r) {
		if (l&1) { ans = MIN(ans, seg[k][l]); ++l; }
		if (r&1) { --r; ans = MIN(ans, seg[k][r]); }
		l /= 2; r /= 2;
	}
	return ans;
}
void up(int k, int i, ll x)
{
	i += N;
	Loop (_,0,18) {
		seg[k][i] = MIN(seg[k][i], x);
		i /= 2;
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int k;
	cin >> n >> k;
	Loop (i,0,n)
		cin >> a[i];
	fill(seg[1], seg[1]+2*N, inf);
	dp[1][0] = a[0];
	up(1, 0, dp[1][0]);
	Loop (i,1,n) {
		dp[1][i] = max(dp[1][i-1], a[i]);
		up(1, i, dp[1][i]);
	}
	Loop (j,1,k) {
		int j2 = j&1;
		fill(seg[!j2], seg[!j2]+2*N, inf);
		dp[!j2][0] = inf;
		vector<int> vec = {0};
		Loop (i,1,n) {
			while (vec.size() && a[vec.back()] < a[i])
				vec.pop_back();
			dp[!j2][i] = get(j2, vec.size()?
					     vec.back():
					     0, i) + a[i];
			if (vec.size()) {
				dp[!j2][i] = min(dp[!j2][i],
					         dp[!j2][vec.back()]);
			}
			up(!j2, i, dp[!j2][i]);
			vec.push_back(i);
		}	
	}
	cout << dp[k&1][n-1] << '\n';
}

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