oj.uz

답안 #681761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681761 2023-01-14T07:50:25 Z pragmatist K개의 묶음 (IZhO14_blocks) C++17
53 / 100
 1000 ms 12212 KB 
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include<bits/stdc++.h>
 
#define ld long double
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)1e6 + 7; // make sure this is right
const int M = (int)1e6 + 7;
const int inf = (int)4e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, k, a[N];
int lo[N], mx[N][20];
ll dp[101][101];

int get(int l, int r) {
	int x = lo[r - l + 1];
	return max(mx[l][x], mx[r - (1 << x) + 1][x]);
}

void solve() {
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		mx[i][0] = a[i];
		dp[i][0] = INF;
	}
	for(int i = 1; i <= k; ++i) dp[0][i] = INF;
	for(int i = 1; i < 20; ++i) {
		for(int j = 1; j <= n - (1 << i) + 1; ++j) {
			mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= k; ++j) {
			dp[i][j] = INF;
			for(int l = i; l >= 1; --l) {
				dp[i][j] = min(dp[i][j], dp[l - 1][j - 1] + get(l, i));
			}
		}
	}	
	
	cout << dp[n][k];
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for(int i = 2; i <= 1e6; ++i) lo[i] = lo[i / 2] + 1;
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 3 ms 4256 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 3 ms 4180 KB Output is correct
12 Correct 3 ms 4260 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct
14 Correct 2 ms 4256 KB Output is correct
15 Correct 3 ms 4256 KB Output is correct
16 Correct 3 ms 4332 KB Output is correct
17 Correct 3 ms 4308 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 3 ms 4200 KB Output is correct
20 Correct 2 ms 4180 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 2 ms 4252 KB Output is correct
24 Correct 3 ms 4256 KB Output is correct
25 Correct 2 ms 4260 KB Output is correct
26 Correct 3 ms 4256 KB Output is correct
27 Correct 3 ms 4180 KB Output is correct
28 Correct 3 ms 4256 KB Output is correct
29 Correct 3 ms 4180 KB Output is correct
30 Correct 3 ms 4264 KB Output is correct
31 Correct 3 ms 4180 KB Output is correct
32 Correct 3 ms 4256 KB Output is correct
33 Correct 3 ms 4180 KB Output is correct
34 Correct 3 ms 4260 KB Output is correct
35 Correct 3 ms 4256 KB Output is correct
36 Correct 3 ms 4180 KB Output is correct
37 Correct 3 ms 4180 KB Output is correct
38 Correct 3 ms 4180 KB Output is correct
39 Correct 4 ms 4260 KB Output is correct
40 Correct 3 ms 4180 KB Output is correct
41 Correct 3 ms 4180 KB Output is correct
42 Correct 2 ms 4180 KB Output is correct
43 Correct 2 ms 4180 KB Output is correct
44 Correct 3 ms 4180 KB Output is correct
45 Correct 2 ms 4264 KB Output is correct
46 Correct 3 ms 4180 KB Output is correct
47 Correct 3 ms 4180 KB Output is correct
48 Correct 3 ms 4180 KB Output is correct
49 Correct 3 ms 4180 KB Output is correct
50 Correct 2 ms 4180 KB Output is correct
51 Correct 3 ms 4308 KB Output is correct
52 Correct 3 ms 4308 KB Output is correct
53 Correct 4 ms 4252 KB Output is correct
54 Correct 4 ms 4308 KB Output is correct
55 Correct 4 ms 4308 KB Output is correct
56 Correct 5 ms 4248 KB Output is correct
57 Correct 5 ms 4264 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 3 ms 4256 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 3 ms 4180 KB Output is correct
12 Correct 3 ms 4260 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct
14 Correct 2 ms 4256 KB Output is correct
15 Correct 3 ms 4256 KB Output is correct
16 Correct 3 ms 4332 KB Output is correct
17 Correct 3 ms 4308 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 3 ms 4200 KB Output is correct
20 Correct 2 ms 4180 KB Output is correct
21 Correct 3 ms 4180 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 2 ms 4252 KB Output is correct
24 Correct 3 ms 4256 KB Output is correct
25 Correct 2 ms 4260 KB Output is correct
26 Correct 3 ms 4256 KB Output is correct
27 Correct 3 ms 4180 KB Output is correct
28 Correct 3 ms 4256 KB Output is correct
29 Correct 3 ms 4180 KB Output is correct
30 Correct 3 ms 4264 KB Output is correct
31 Correct 3 ms 4180 KB Output is correct
32 Correct 3 ms 4256 KB Output is correct
33 Correct 3 ms 4180 KB Output is correct
34 Correct 3 ms 4260 KB Output is correct
35 Correct 3 ms 4256 KB Output is correct
36 Correct 3 ms 4180 KB Output is correct
37 Correct 3 ms 4180 KB Output is correct
38 Correct 3 ms 4180 KB Output is correct
39 Correct 4 ms 4260 KB Output is correct
40 Correct 3 ms 4180 KB Output is correct
41 Correct 3 ms 4180 KB Output is correct
42 Correct 2 ms 4180 KB Output is correct
43 Correct 2 ms 4180 KB Output is correct
44 Correct 3 ms 4180 KB Output is correct
45 Correct 2 ms 4264 KB Output is correct
46 Correct 3 ms 4180 KB Output is correct
47 Correct 3 ms 4180 KB Output is correct
48 Correct 3 ms 4180 KB Output is correct
49 Correct 3 ms 4180 KB Output is correct
50 Correct 2 ms 4180 KB Output is correct
51 Correct 3 ms 4308 KB Output is correct
52 Correct 3 ms 4308 KB Output is correct
53 Correct 4 ms 4252 KB Output is correct
54 Correct 4 ms 4308 KB Output is correct
55 Correct 4 ms 4308 KB Output is correct
56 Correct 5 ms 4248 KB Output is correct
57 Correct 5 ms 4264 KB Output is correct
58 Execution timed out 1093 ms 12212 KB Time limit exceeded
59 Halted 0 ms 0 KB -