oj.uz

답안 #162996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162996 2019-11-10T17:19:27 Z mosiashvililuka K개의 묶음 (IZhO14_blocks) C++14
53 / 100
 1000 ms 55032 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++){
			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.0 / 14.0

# 결과 실행 시간 메모리 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 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 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 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 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 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5880 KB Output is correct
2 Correct 40 ms 21724 KB Output is correct
3 Correct 67 ms 24696 KB Output is correct
4 Correct 352 ms 24824 KB Output is correct
5 Execution timed out 1075 ms 55032 KB Time limit exceeded
6 Halted 0 ms 0 KB -