Submission #646274

#	Time	Username	Problem	Language	Result	Execution time	Memory
646274		ymm	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	340 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 = 100'010;
const int K = 110;
const ll inf = 1e15;
ll dp[K][N];
ll a[N];
int n;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
ll get_max(int l, int r)
{
	ll ans = 0;
	Loop (i,l,r)
		ans = a[i] > ans? a[i]: ans;
	return ans;
}

void up_dp(int k, int l, int r, int pl, int pr)
{
	if (r <= l)
		return;
	int mid = (l + r)/2;
	ll mn = inf, mnp = -1;
	ll mx = pr < mid? get_max(pr, mid): 0;
	LoopR (i,pl,min(pr,mid)) {
		mx = max(mx, a[i]);
		if (mx + dp[k-1][i] < mn) {
			mnp = i;
			mn = mx + dp[k-1][i];
		}
	}
	dp[k][mid] = mn;
	up_dp(k, l, mid, pl, mnp+1);
	up_dp(k, mid+1, r, mnp, pr);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int k;
	cin >> n >> k;
	Loop (i,0,n)
		cin >> a[i];
	dp[1][1] = a[0];
	Loop (i,1,n)
		dp[1][i+1] = max(dp[1][i], a[i]);
	Loop (i,2,k+1)
		up_dp(i, i, n+1, i-1, n);
	cout << dp[k][n] << '\n';
}

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