Submission #162937

#	Time	Username	Problem	Language	Result	Execution time	Memory
162937		mosiashvililuka	K blocks (IZhO14_blocks)	C++14	0 / 100	37 ms	10972 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;
vector <pair <int, int> > vv[100009];
vector <int> v[100009];
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);
		vv[d].push_back(make_pair(f[c],c));
		msh[c]=d;
//		cout<<msh[c]<<endl;
		upd(m[f[c]],c);
	}
	for(c=0; c<=a; c++) sort(vv[c].begin(),vv[c].end());
	for(c=0; c<=a; c++){
		for(d=0; d<vv[c].size(); d++){
			v[c].push_back(vv[c][d].second);
		}
	}
	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];
				}
			}
		}
//		cout<<rm[2][2]<<endl;
		for(d=1; d<=a; d++){
			zx=d-msh[d];
			dp[d][c]=min(rm[msh[d]][ka[zx]],rm[d-(1<<ka[zx])+1][ka[zx]])+f[d];
//			cout<<min(rm[msh[d]][ka[zx]],rm[d-(1<<ka[zx])+1][ka[zx]])<<endl;
			if(dp[d][c]>dp[msh[d]][c]) dp[d][c]=dp[msh[d]][c];
		}
	}
	cout<<dp[a][b];
	return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:54:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(d=0; d<vv[c].size(); d++){
            ~^~~~~~~~~~~~~

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