Submission #688611

#	Time	Username	Problem	Language	Result	Execution time	Memory
688611		luka1234	K blocks (IZhO14_blocks)	C++14	0 / 100	24 ms	39860 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;
int n,m;
int a[100001];
int dp[100001][101];
int t[101][400001];
int marc[100001];
void update(int v,int tl,int tr,int pos,int x,int ind){
	if(tl==tr){
		t[ind][v]=x;
	}
	else{
		int 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]);
	}
}
int get(int v,int tl,int tr,int l,int r,int ind){
	if(r<tl||l>tr){
		return 1e9;
	}
	if(l>=tl&&r<=tr){
		return t[ind][v];
	}
	int m=(tl+tr)/2;
	int f1=get(2*v,tl,m,l,r,ind);
	int f2=get(2*v+1,m+1,tr,l,r,ind);
	int f=min(f1,f2);
	return f;
}
void make(){
	stack<int> st;
	for(int k=n;k>=1;k--){
		while(!st.empty()&&a[k]>a[st.top()]){
			marc[st.top()]=k;
			st.pop();
		}
		st.push(k);
	}
}
int main(){
	for(int i=0;i<=100000;i++){
		for(int j=0;j<=100;j++){
			dp[i][j]=1e9;
		}
	}
	cin>>n>>m;
	int mx=0;
	for(int 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(int k=2;k<=m;k++){
		for(int i=k;i<=n;i++){
			int f=marc[i];
			int mn=get(1,1,n,f+1,i,k-1);
			mn=mn+a[i];
			int 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;
}

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