Submission #1208825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208825		gatapdev	K blocks (IZhO14_blocks)	C++20	0 / 100	2 ms	4936 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+9;
int n,K;
int a[N];
vector<int> st(4*N);
vector<int> dp_before(N),dp_cur(N); 
int C(int l,int r);
void compute(int l,int r,int optl,int optr);
void build(int id,int l,int r);
int get(int id,int l,int r,int u,int v);
int solve1();
signed main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,0,n);	
	for(int i=0;i<=n;i++){
		dp_before[i]=C(0,i);
	}
	for(int i=2;i<=K;i++){
		compute(0,n,0,n);
		dp_before=dp_cur;
	}
	cout<<dp_before[n];
}
int solve1(){
	vector<vector<int>> dp(n+10,vector<int>(K+10,0));
	for(int i=1;i<=n;i++) for(int j=1;j<=K;j++) dp[i][j]=INT_MAX;
	for(int i=1;i<=n;i++) dp[i][1]=max(dp[i-1][1],a[i]);
	for(int i=1;i<=n;i++){
		for(int j=2;j<=i;j++){
			int mx=-1;
			for(int k=j;k<=i;k++) mx=max(mx,a[k]);
			for(int k=2;k<=min(i,K);k++){
				dp[i][k]=min(dp[i][k],dp[j-1][k-1]+mx);
			}
		}
	} 
	return dp[n][K];
}
void build(int id,int l,int r){
	if(l==r){
		st[id]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
	if(l>v||r<u) return INT_MIN;
	if(l>=u&&r<=v) return st[id];
	int mid=(r+l)/2;
	int get1=get(id*2,l,mid,u,v);
	int get2=get(id*2+1,mid+1,r,u,v);
	return max(get1,get2);
}
int C(int l,int r){
	return get(1,0,n,l,r);
}
void compute(int l,int r,int optl,int optr){
	if(l>r) return;
	int mid=(l+r)/2;
	pair<int,int> best={INT_MAX,-1};
	for(int k=optl;k<=min(mid,optr);k++){
		if(k>1)
		best=min(best,{dp_before[k-1]+C(k,mid),k});
	}
	dp_cur[mid]=best.first;
	int opt=best.second;
	compute(l,mid-1,optl,opt);
	compute(mid+1,r,opt,optr);
}

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