Submission #1208792

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

blocks

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100001];
vector<int> dp_before(1001+1),dp_cur(1001+1); 
int C(int l,int r);
void compute(int l,int r,int optl,int optr);
signed main(){
	int n,K;
	cin>>n>>K;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		dp_before[i]=C(1,i);
	}
	for(int i=1;i<=K;i++){
		compute(0,n,0,n);
		dp_before=dp_cur;
	}
	cout<<dp_before[n];
}
int C(int l,int r){
	int ans=-1;
	for(int i=l;i<=r;i++) ans=max(ans,a[i]);
	return ans;
}
void compute(int l,int r,int optl,int optr){
	if(l>r) return;
	int mid=(l+r)>>1;
	pair<int,int> best={INT_MAX,-1};
	for(int k=optl;k<=min(mid,optr);k++){
		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