제출 #1285305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285305		Jawad_Akbar_JJ	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	537 ms	55256 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;

		vector<int> vc = {0}, mn = {ft[1]};
		for (int i=1;i<=n;i++){
			dp[i][j] = get(prv[i]) + a[i];

			while (vc.size() > 1 and a[vc.back()] <= a[i]){
				if (a[vc.back()] == a[i])
					dp[i][j] = min(dp[i][j], mn.back());
				vc.pop_back();
				mn.pop_back();
			}
			dp[i][j] = min(dp[i][j], mn.back());
			vc.push_back(i);
			mn.push_back(min(mn.back(), dp[i][j]));

			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: 47 / 47