제출 #162996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162996		mosiashvililuka	K blocks (IZhO14_blocks)	C++14	53 / 100	1075 ms	55032 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f[100009],dp[100009][109],mxa,fen[100009],msh[100009],rm[100009][17],zxc,zx,xc,ka[100009];
map <int, int> m;
map <int, int>::iterator itt;
void upd(int q, int w){
	q=a+1-q;
	while(q<=a+2){
		fen[q]=w;
		q=q+(q&(-q));
	}
}
int read(int q){
	q=a-q+1;
	if(q<=0) return 0;
	int mxpa=0;
	while(q>=1){
		if(fen[q]>mxpa) mxpa=fen[q];
		q=q-(q&(-q));
	}
	return mxpa;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(c=1; c<=a; c++){
		cin>>f[c];
		m[f[c]]=1;
		if(mxa<f[c]) mxa=f[c];
	}
	c=0;
	for(itt=m.begin(); itt!=m.end(); itt++){
		c++;
		m[(*itt).first]=c;
	}
	ka[0]=0;
	for(c=1; c<=a+2; c++){
		if((1<<ka[c-1])*2<c) ka[c]=ka[c-1]+1; else ka[c]=ka[c-1];
	}
	for(c=0; c<=a+3; c++){
		fen[c]=0;
	}
	for(c=1; c<=a; c++){
		d=read(m[f[c]]+1);
		msh[c]=d;
		upd(m[f[c]],c);
	}
	for(d=0; d<=a; d++){
	    for(c=0; c<=b; c++) dp[d][c]=999999999;
	}
	d=0;
	for(c=1; c<=a; c++){
		if(d<f[c]) d=f[c];
		dp[c][1]=d;
	}
	if(b==1){
		cout<<dp[a][1];
		return 0;
	}
	for(c=2; c<=b; c++){
		for(d=0; d<=a; d++) rm[d][0]=dp[d][c-1];
		for(e=1; e<=16; e++){
			zx=a-(1<<e)+1;
			for(d=0; d<=zx; d++){
				if(rm[d][e-1]<rm[d+(1<<(e-1))][e-1]){
					rm[d][e]=rm[d][e-1];
				}else{
					rm[d][e]=rm[d+(1<<(e-1))][e-1];
				}
			}
		}
		for(d=1; d<=a; d++){
			zx=d-msh[d];
			dp[d][c]=min(rm[msh[d]][ka[zx]],rm[d-(1<<ka[zx])][ka[zx]])+f[d];
			if(dp[d][c]>dp[msh[d]][c]) dp[d][c]=dp[msh[d]][c];
		}
	}
	cout<<dp[a][b];
	return 0;
}

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