Submission #1285287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285287		Jawad_Akbar_JJ	K blocks (IZhO14_blocks)	C++20	53 / 100	1094 ms	56112 KiB

blocks

#include <iostream>
#include <queue>

using namespace std;
const int N = 1<<17;
int dp[N][102], a[N], ft[N], prv[N], nxt[N];
vector<int> v1, v2;

void Add(int i, int vl){
	for (;i; i -= i & -i)
		ft[i] = min(ft[i], vl);
}

int get(int i, int ans = 1e9){
	for (;i<N;i += i & -i)
		ans = min(ans, ft[i]);
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
	int n, k;
	cin>>n>>k;

	for (int i=1, mx = 0;i<=n;i++){
		cin>>a[i];
		mx = max(mx, a[i]);
		
		dp[i][1] = mx;

		while (v1.size() > 0 and a[i] > a[v1.back()])
			nxt[v1.back()] = i, v1.pop_back();
		v1.push_back(i), nxt[i] = n + 1;
	}

	for (int i=n;i>=1;i--){
		while (v2.size() > 0 and a[i] > a[v2.back()])
			prv[v2.back()] = i, v2.pop_back();
		v2.push_back(i), prv[i] = 1;
	}

	for (int j=2;j<=k;j++){
		for (int i=1;i<N;i++)
			ft[i] = dp[i][j] = 1e9;

		priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
		for (int i=1;i<=n;i++){
			while (pq.size() > 0 and nxt[pq.top().second] <= i)
				pq.pop();

			dp[i][j] = get(prv[i]) + a[i];
			if (pq.size() > 0)
				dp[i][j] = min(dp[i][j], pq.top().first);

			pq.push({dp[i][j], i});
			Add(i, dp[i][j-1]);
		}
	}

	cout<<dp[n][k]<<'\n';
}

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