Submission #688615

#	Time	Username	Problem	Language	Result	Execution time	Memory
688615		luka1234	K blocks (IZhO14_blocks)	C++14	0 / 100	41 ms	79380 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
ll n,m;
ll a[100001];
ll dp[100001][101];
ll t[101][400001];
ll marc[100001];
void update(ll v,ll tl,ll tr,ll pos,ll x,ll ind){
	if(tl==tr){
		t[ind][v]=x;
	}
	else{
		ll m=(tl+tr)/2;
		if(pos<=m){
			update(2*v,tl,m,pos,x,ind);
		}
		else{
			update(2*v+1,m+1,tr,pos,x,ind);
		}
		t[ind][v]=min(t[ind][2*v],t[ind][2*v+1]);
	}
}
ll get(ll v,ll tl,ll tr,ll l,ll r,ll ind){
	if(r<tl||l>tr){
		return 1e18;
	}
	if(l>=tl&&r<=tr){
		return t[ind][v];
	}
	ll m=(tl+tr)/2;
	ll f1=get(2*v,tl,m,l,r,ind);
	ll f2=get(2*v+1,m+1,tr,l,r,ind);
	ll f=min(f1,f2);
	return f;
}
void make(){
	stack<ll> st;
	for(ll k=n;k>=1;k--){
		while(!st.empty()&&a[k]>a[st.top()]){
			int f=a[st.top()];
			marc[st.top()]=k;
			st.pop();
		}
		st.push(k);
	}
}
int main(){
	for(ll i=0;i<=100000;i++){
		for(ll j=0;j<=100;j++){
			dp[i][j]=1e18;
		}
	}
	cin>>n>>m;
	ll mx=0;
	for(ll k=1;k<=n;k++){
		cin>>a[k];
		mx=max(mx,a[k]);
		dp[k][1]=mx;
		update(1,1,n,k,mx,1);
	}
	make();
	for(ll k=2;k<=m;k++){
		for(ll i=k;i<=n;i++){
			ll f=marc[i];
			if(f==i-1){
				ll mn=dp[i-1][k];
				dp[i][k]=mn;
				update(1,1,n,i,mn,k);
				continue;
			}
			ll mn=get(1,1,n,f+1,i-1,k-1);
			mn=mn+a[i];
			ll f1=dp[f][k];
			mn=min(mn,f1);
			dp[i][k]=mn;
			update(1,1,n,i,mn,k);
		}
	}
	cout<<dp[n][m];
    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'void make()':
blocks.cpp:48:8: warning: unused variable 'f' [-Wunused-variable]
   48 |    int f=a[st.top()];
      |        ^

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