답안 #1101457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101457	2024-10-16T08:43:45 Z	LOLOLO	K개의 묶음 (IZhO14_blocks)	C++14	0 / 100	12 ms	83792 KB

blocks

#include <bits/stdc++.h>
#define int long long
#define f first
#define pii pair<int, int>
#define s second
 
const int N = 1e5 + 5;
const int block = 450;
const int oo = 99999989;
const int base = 31;
 
using namespace std;
 
int n, a[N], dp[N][105], rmq[N][20], k;
 
int get(int l, int r){
	if(r == l) return rmq[l][0];
	int k = __lg(r - l + 1);
	return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
 
signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
 
	
	cin >> n >> k;
	for(int i = 1;i <= n;i++) cin >> a[i], rmq[i][0] = a[i];
	
	for(int j = 1;(1 << j) <= n;j++){
		for(int i = 1; i + (1 << j) - 1 <= n;i++){
			rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
	
	memset(dp, 0x4f, sizeof(dp));
	dp[0][1] = 0;
	for(int i = 1;i <= n;i++) dp[i][1] = max(dp[i - 1][1], a[i]);
	
	
	for(int j = 2;j <= k;j++){
		for(int i = j;i <= n;i++){
			for(int h = max(j, i - 5);h <= i;h++){
				dp[i][j] = min(dp[i][j], dp[h - 1][j - 1] + get(h,  i));
			}
		}
	}
	cout << dp[n][k];
	return 0;
}
 

Subtask #1

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	83536 KB	Output is correct
2	Correct	11 ms	83772 KB	Output is correct
3	Correct	10 ms	83536 KB	Output is correct
4	Correct	10 ms	83728 KB	Output is correct
5	Correct	11 ms	83552 KB	Output is correct
6	Correct	11 ms	83536 KB	Output is correct
7	Correct	10 ms	83536 KB	Output is correct
8	Correct	12 ms	83536 KB	Output is correct
9	Correct	11 ms	83536 KB	Output is correct
10	Correct	11 ms	83768 KB	Output is correct
11	Correct	10 ms	83536 KB	Output is correct
12	Correct	10 ms	83792 KB	Output is correct
13	Incorrect	11 ms	83536 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #2

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	83536 KB	Output is correct
2	Correct	11 ms	83536 KB	Output is correct
3	Correct	11 ms	83608 KB	Output is correct
4	Correct	10 ms	83536 KB	Output is correct
5	Correct	11 ms	83704 KB	Output is correct
6	Correct	10 ms	83536 KB	Output is correct
7	Correct	11 ms	83536 KB	Output is correct
8	Correct	11 ms	83536 KB	Output is correct
9	Correct	10 ms	83536 KB	Output is correct
10	Correct	10 ms	83536 KB	Output is correct
11	Correct	11 ms	83536 KB	Output is correct
12	Correct	10 ms	83632 KB	Output is correct
13	Correct	11 ms	83536 KB	Output is correct
14	Correct	10 ms	83536 KB	Output is correct
15	Correct	11 ms	83572 KB	Output is correct
16	Correct	11 ms	83536 KB	Output is correct
17	Correct	10 ms	83536 KB	Output is correct
18	Incorrect	11 ms	83760 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	83536 KB	Output is correct
2	Correct	11 ms	83772 KB	Output is correct
3	Correct	10 ms	83536 KB	Output is correct
4	Correct	10 ms	83728 KB	Output is correct
5	Correct	11 ms	83552 KB	Output is correct
6	Correct	11 ms	83536 KB	Output is correct
7	Correct	10 ms	83536 KB	Output is correct
8	Correct	12 ms	83536 KB	Output is correct
9	Correct	11 ms	83536 KB	Output is correct
10	Correct	11 ms	83768 KB	Output is correct
11	Correct	10 ms	83536 KB	Output is correct
12	Correct	10 ms	83792 KB	Output is correct
13	Incorrect	11 ms	83536 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	83536 KB	Output is correct
2	Correct	11 ms	83772 KB	Output is correct
3	Correct	10 ms	83536 KB	Output is correct
4	Correct	10 ms	83728 KB	Output is correct
5	Correct	11 ms	83552 KB	Output is correct
6	Correct	11 ms	83536 KB	Output is correct
7	Correct	10 ms	83536 KB	Output is correct
8	Correct	12 ms	83536 KB	Output is correct
9	Correct	11 ms	83536 KB	Output is correct
10	Correct	11 ms	83768 KB	Output is correct
11	Correct	10 ms	83536 KB	Output is correct
12	Correct	10 ms	83792 KB	Output is correct
13	Incorrect	11 ms	83536 KB	Output isn't correct
14	Halted	0 ms	0 KB	-