Submission #1180238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180238		altern23	K blocks (IZhO14_blocks)	C++17	53 / 100	1095 ms	8904 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 4e18;
const int MOD = 998244353;

struct ST{
	ll n;
	vector<ll> sg;
	ST(ll _n){
		n = _n;
		sg.resize(4 * n + 5);
	}
	void upd(ll l, ll r, ll cur, ll idx, ll val){
		if(l == r) sg[cur] = val;
		else{
			ll mid = (l + r) / 2;
			if(idx <= mid) upd(l, mid, cur * 2, idx, val);
			else upd(mid + 1, r, cur * 2 + 1, idx, val);
			sg[cur] = min(sg[cur * 2], sg[cur * 2 + 1]);
		}
	}
	ll query(ll l, ll r, ll cur, ll x, ll y){
		if(l > y || r < x) return INF;
		if(l >= x && r <= y) return sg[cur];
		ll mid = (l + r) / 2;
		return min(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;		
	for(;tc--;){
		ll N, K; cin >> N >> K;
		vector<ll> a(N + 5), lf(N + 5, 1), rg(N + 5, N);
		for(int i = 1; i <= N; i++) cin >> a[i];
		stack<ll> stk;
		for(int i = 1; i <= N; i++){
			while(!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
			if(!stk.empty()) lf[i] = stk.top() + 1;
			stk.push(i);
		}
		while(!stk.empty()) stk.pop();
		for(int i = N; i >= 1; --i){
			while(!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
			if(!stk.empty()) rg[i] = stk.top() - 1;
			stk.push(i);
		}
		vector<ll> dp(N + 5, INF);
		dp[0] = 0;
		ST sg(N + 1);
		for(int i = 0; i <= N; i++) sg.upd(0, N, 1, i, dp[i]);
		for(int i = 1; i <= K; i++){
			vector<ll> ndp(N + 5, INF);
			priority_queue<pii, vector<pii>, greater<pii>> pq;
			for(int j = 1; j <= N; j++){
				ll val = sg.query(0, N, 1, lf[j] - 1, j - 1);
				pq.push({val + a[j], rg[j]});
				while(pq.top().sec < j) pq.pop();
				ndp[j] = pq.top().fi;
			}
			for(int j = 0; j <= N; j++) sg.upd(0, N, 1, j, ndp[j]);
			dp.swap(ndp);
		}
		
		cout << dp[N] << "\n";
	}
}

/*
1 2 3 4 5 6 7
*/

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