답안 #41286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41286	2018-02-15T11:54:16 Z	IvanC	K개의 묶음 (IZhO14_blocks)	C++14	53 / 100	1000 ms	1364 KB

blocks

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int INF = 1e9;
const int MAXN = 1e5  + 10;
const int MAXK = 101;
int vetor[MAXN],dp[MAXK][MAXN],N,K,seg[4*MAXN];
void build(int pos,int left,int right){
	if(left == right){
		seg[pos] = vetor[left];
		return;
	}
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = max(seg[2*pos],seg[2*pos+1]);
}
int query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j) return seg[pos];
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	return max(query(2*pos,left,mid,i,j),query(2*pos+1,mid+1,right,i,j));
}
int main(){
	scanf("%d %d",&N,&K);
	for(int i = 1;i<=N;i++) scanf("%d",&vetor[i]);
	build(1,1,N);
	for(int i = 1;i<=N;i++){
		dp[1][i] = query(1,1,N,1,i);
	}
	for(int k = 2;k<=K;k++){
		for(int i = k;i<=N;i++){
			dp[k][i] = INF;
			for(int j = k-1;j<i;j++){
				dp[k][i] = min(dp[k][i], dp[k-1][j] + query(1,1,N,j+1,i) );
			}
		}
	}
	printf("%d\n",dp[K][N]);
	return 0;
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:26:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&K);
                      ^
blocks.cpp:27:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i<=N;i++) scanf("%d",&vetor[i]);
                                               ^

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	1 ms	408 KB	Output is correct
4	Correct	2 ms	520 KB	Output is correct
5	Correct	2 ms	520 KB	Output is correct
6	Correct	1 ms	528 KB	Output is correct
7	Correct	1 ms	532 KB	Output is correct
8	Correct	1 ms	532 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	2 ms	608 KB	Output is correct
13	Correct	3 ms	640 KB	Output is correct
14	Correct	3 ms	676 KB	Output is correct
15	Correct	2 ms	764 KB	Output is correct
16	Correct	2 ms	764 KB	Output is correct
17	Correct	2 ms	764 KB	Output is correct
18	Correct	3 ms	764 KB	Output is correct

Subtask #2

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	764 KB	Output is correct
2	Correct	1 ms	764 KB	Output is correct
3	Correct	2 ms	764 KB	Output is correct
4	Correct	1 ms	764 KB	Output is correct
5	Correct	2 ms	848 KB	Output is correct
6	Correct	2 ms	848 KB	Output is correct
7	Correct	2 ms	848 KB	Output is correct
8	Correct	1 ms	848 KB	Output is correct
9	Correct	1 ms	848 KB	Output is correct
10	Correct	1 ms	848 KB	Output is correct
11	Correct	2 ms	848 KB	Output is correct
12	Correct	2 ms	848 KB	Output is correct
13	Correct	2 ms	848 KB	Output is correct
14	Correct	2 ms	848 KB	Output is correct
15	Correct	2 ms	848 KB	Output is correct
16	Correct	2 ms	848 KB	Output is correct
17	Correct	2 ms	848 KB	Output is correct
18	Correct	2 ms	848 KB	Output is correct
19	Correct	2 ms	848 KB	Output is correct
20	Correct	2 ms	848 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	912 KB	Output is correct
2	Correct	2 ms	912 KB	Output is correct
3	Correct	2 ms	912 KB	Output is correct
4	Correct	2 ms	912 KB	Output is correct
5	Correct	2 ms	912 KB	Output is correct
6	Correct	2 ms	912 KB	Output is correct
7	Correct	2 ms	912 KB	Output is correct
8	Correct	2 ms	912 KB	Output is correct
9	Correct	2 ms	912 KB	Output is correct
10	Correct	2 ms	912 KB	Output is correct
11	Correct	2 ms	912 KB	Output is correct
12	Correct	2 ms	912 KB	Output is correct
13	Correct	9 ms	956 KB	Output is correct
14	Correct	10 ms	960 KB	Output is correct
15	Correct	15 ms	1220 KB	Output is correct
16	Correct	15 ms	1224 KB	Output is correct
17	Correct	14 ms	1224 KB	Output is correct
18	Correct	16 ms	1224 KB	Output is correct
19	Correct	16 ms	1364 KB	Output is correct

Subtask #4

0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1067 ms	1364 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-