oj.uz

Submission #166856

# Submission time Handle Problem Language Result Execution time Memory
166856 2019-12-04T11:51:56 Z mosiashvililuka K blocks (IZhO14_blocks) C++14
0 / 100
 13 ms 5112 KB 
#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++){
			dp[d][c]=dp[msh[d]][c-1]+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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -