Submission #1208857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208857		gatapdev	K blocks (IZhO14_blocks)	C++20	53 / 100	1094 ms	5192 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
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 solve();
signed main(){
	cin>>n>>K;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<solve();
}
int solve(){
	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;
	}
	return dp_before[n];
}
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=1;k<=mid;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: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47