제출 #1198468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198468		steve_csp	K개의 묶음 (IZhO14_blocks)	C++17	0 / 100	3 ms	3656 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
//#define ll long long//#define fi first//#define se second
#define ll long long
#define memaybeo main
#define en "\n";
#define hackspeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define dafug return 0;
const int mmb = 1e5+2;
int n,k,a[mmb],lef[mmb];
ll seg[4*mmb],dp[mmb][102];
void update(int x,int l,int r,int i,int vl) 
{
    if (l == r) { seg[x] = vl; return; }
    int m = (l+r)/2;
    if (i <= m) update(2*x,l,m,i,vl);
    else update(2*x+1,m+1,r,i,vl);
    seg[x] = min(seg[2*x],seg[2*x+1]);
}
ll MIN(int x,int l,int r,int i,int j) 
{
    if (j < l || i > r) return 1e18;
    if (i <= l && j >= r) return seg[x];
    int m = (l+r)/2;
    return min(MIN(2*x,l,m,i,j) , MIN(2*x+1,m+1,r,i,j));
}
void dopdop()
{
	cin >> n >> k;fill(dp[0],dp[0]+k+1,(ll)1e18);
	for(int i=1;i<=n;++i) cin >> a[i] , fill(dp[i],dp[i]+k+1,(ll)1e18);
	dp[1][1] = a[1];
	for(int i=2;i<=n;++i) dp[i][1] = max((ll)a[i],dp[i-1][1]);
	///////////////
	stack<int> st;
	for(int i=n;i>0;--i) 
	{
		while(!st.empty() && a[i] > a[st.top()]) lef[st.top()] = i , st.pop();
		st.push(i);
	}
	while(!st.empty()) lef[st.top()] = 0 , st.pop();
	//cout << en;for(int i=1;i<=n;++i) cout << lef[i] << ' ';cout << en;
	//////////////
	for(int j=2;j<=k;++j)
	{
		fill(seg,seg+4*mmb,(ll)1e18);
		for(int i=1;i<j;++i) update(1,1,n,i,dp[i][j-1]);// , cout << dp[i][j-1] << en;
		//cout << MIN(1,1,n,1,1) << en;
		for(int i=j;i<=n;++i) 	
		{
			int lim = max(lef[i],j-1);
			dp[i][j] = min(MIN(1,1,n,lim,i-1) + (ll)a[i] , dp[lef[i]][k]);
			//cout << MIN(1,1,n,lim,i-1) << ' ' << lim << ' ' << i-1 << en;
			update(1,1,n,i,dp[i][j-1]);
		}
	}
	/*cout << en;
	for(int i=1;i<=n;++i) 
	{
		for(int j=1;j<=k;++j) cout << dp[i][j] << ' ';cout << en;
	}*/
	cout << dp[n][k];
}
signed memaybeo()
{
	hackspeed
	//skibidi();
	dopdop();
	//yesyes();
	dafug
}

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