제출 #1282532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282532		bobothenubchick	K개의 묶음 (IZhO14_blocks)	C++20	53 / 100	1113 ms	299584 KiB

blocks

# include <bits/stdc++.h>
using namespace std;
#define int long long

int k,n,a[100005],dp[100005][105],b[400005][105],l[100005],res;
stack<int> g;

void update(int id, int l, int r, int pos, int kk, int val)
{
	if (pos < l or r < pos) return;
	if (l==r)
	{
		b[id][kk] = val;
		return;
	}
	int mid = (l+r)/2;
	update(id*2,l,mid,pos,kk,val); update(id*2+1,mid+1,r,pos,kk,val);
	b[id][kk] = min(b[id*2][kk],b[id*2+1][kk]);
}

int get(int id, int l, int r, int u, int v, int kk)
{
    if (r < u or v < l) return 1e9;
    if (u <= l and r <= v)
    {
        return b[id][kk];
    }
    int mid = (l+r)/2;
    int q = get(id*2,l,mid,u,v,kk), p = get(id*2+1,mid+1,r,u,v,kk);
    return min(p,q);
}


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		while (!g.empty() and a[g.top()] <= a[i]) g.pop();
		if (g.empty()) l[i] = 0;
		else l[i] = g.top();	
		g.push(i);
	}
	for (int i =0; i <= n; i++) for (int j = 0; j <= k; j++) dp[i][j] = 1e9;
	dp[0][0] = 0;
	dp[1][1] = a[1];
	update(1,1,n,1,1,dp[1][1]);
	for (int i = 2; i <= n; i++)
	{
		dp[i][1] = max(dp[i-1][1],a[i]);
		update(1,1,n,i,1,dp[i][1]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 2; j <= k; j++)
		{
			// dp[i][j] = min(dp[l[i]][j-1],dp[p][j-1] + a[i] (p thuoc {l[i]+1,i}));
			dp[i][j] = dp[l[i]][j];
			if (l[i] <= i-1)
			{
				dp[i][j] = min(dp[i][j],get(1,1,n,max(l[i],j-1),i-1,j-1)+a[i]);
			}
			update(1,1,n,i,j,dp[i][j]);
		}
	}
	// dp[i][j] la so tien nho nhat xet den vi tri i va da chia dc j doan
	cout << dp[n][k];
}

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