oj.uz

Submission #682020

# Submission time Handle Problem Language Result Execution time Memory
682020 2023-01-15T09:06:23 Z acm K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 12684 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[20][N];
ll dp[101][101];
 
int get(int l, int r) {
	int x = lo[r - l + 1];
	return max(mx[x][l], mx[x][r - (1 << x) + 1]);
}
 
void solve() {
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		mx[0][i] = 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[i][j] = max(mx[i - 1][j], mx[i - 1][j + (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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4252 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4256 KB Output is correct
7 Correct 3 ms 4260 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 4384 KB Output is correct
13 Correct 3 ms 4376 KB Output is correct
14 Correct 3 ms 4308 KB Output is correct
15 Correct 3 ms 4436 KB Output is correct
16 Correct 3 ms 4380 KB Output is correct
17 Correct 3 ms 4384 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 4 ms 4164 KB Output is correct
4 Correct 3 ms 4180 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 3 ms 4256 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 3 ms 4260 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 4180 KB Output is correct
13 Correct 3 ms 4176 KB Output is correct
14 Correct 3 ms 4256 KB Output is correct
15 Correct 3 ms 4256 KB Output is correct
16 Correct 3 ms 4308 KB Output is correct
17 Correct 3 ms 4308 KB Output is correct
18 Correct 3 ms 4256 KB Output is correct
19 Correct 3 ms 4308 KB Output is correct
20 Correct 3 ms 4296 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4252 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4256 KB Output is correct
7 Correct 3 ms 4260 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 4384 KB Output is correct
13 Correct 3 ms 4376 KB Output is correct
14 Correct 3 ms 4308 KB Output is correct
15 Correct 3 ms 4436 KB Output is correct
16 Correct 3 ms 4380 KB Output is correct
17 Correct 3 ms 4384 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 4 ms 4180 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 4 ms 4164 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 3 ms 4180 KB Output is correct
24 Correct 3 ms 4180 KB Output is correct
25 Correct 3 ms 4256 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct
27 Correct 3 ms 4260 KB Output is correct
28 Correct 3 ms 4180 KB Output is correct
29 Correct 3 ms 4180 KB Output is correct
30 Correct 3 ms 4180 KB Output is correct
31 Correct 3 ms 4176 KB Output is correct
32 Correct 3 ms 4256 KB Output is correct
33 Correct 3 ms 4256 KB Output is correct
34 Correct 3 ms 4308 KB Output is correct
35 Correct 3 ms 4308 KB Output is correct
36 Correct 3 ms 4256 KB Output is correct
37 Correct 3 ms 4308 KB Output is correct
38 Correct 3 ms 4296 KB Output is correct
39 Correct 3 ms 4308 KB Output is correct
40 Correct 3 ms 4256 KB Output is correct
41 Correct 3 ms 4180 KB Output is correct
42 Correct 3 ms 4252 KB Output is correct
43 Correct 3 ms 4252 KB Output is correct
44 Correct 3 ms 4180 KB Output is correct
45 Correct 3 ms 4180 KB Output is correct
46 Correct 3 ms 4256 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 3 ms 4176 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 4308 KB Output is correct
54 Correct 4 ms 4384 KB Output is correct
55 Correct 3 ms 4380 KB Output is correct
56 Correct 4 ms 4380 KB Output is correct
57 Correct 4 ms 4308 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 3 ms 4252 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 3 ms 4256 KB Output is correct
7 Correct 3 ms 4260 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 4384 KB Output is correct
13 Correct 3 ms 4376 KB Output is correct
14 Correct 3 ms 4308 KB Output is correct
15 Correct 3 ms 4436 KB Output is correct
16 Correct 3 ms 4380 KB Output is correct
17 Correct 3 ms 4384 KB Output is correct
18 Correct 3 ms 4308 KB Output is correct
19 Correct 4 ms 4180 KB Output is correct
20 Correct 3 ms 4180 KB Output is correct
21 Correct 4 ms 4164 KB Output is correct
22 Correct 3 ms 4180 KB Output is correct
23 Correct 3 ms 4180 KB Output is correct
24 Correct 3 ms 4180 KB Output is correct
25 Correct 3 ms 4256 KB Output is correct
26 Correct 3 ms 4180 KB Output is correct
27 Correct 3 ms 4260 KB Output is correct
28 Correct 3 ms 4180 KB Output is correct
29 Correct 3 ms 4180 KB Output is correct
30 Correct 3 ms 4180 KB Output is correct
31 Correct 3 ms 4176 KB Output is correct
32 Correct 3 ms 4256 KB Output is correct
33 Correct 3 ms 4256 KB Output is correct
34 Correct 3 ms 4308 KB Output is correct
35 Correct 3 ms 4308 KB Output is correct
36 Correct 3 ms 4256 KB Output is correct
37 Correct 3 ms 4308 KB Output is correct
38 Correct 3 ms 4296 KB Output is correct
39 Correct 3 ms 4308 KB Output is correct
40 Correct 3 ms 4256 KB Output is correct
41 Correct 3 ms 4180 KB Output is correct
42 Correct 3 ms 4252 KB Output is correct
43 Correct 3 ms 4252 KB Output is correct
44 Correct 3 ms 4180 KB Output is correct
45 Correct 3 ms 4180 KB Output is correct
46 Correct 3 ms 4256 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 3 ms 4176 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 4308 KB Output is correct
54 Correct 4 ms 4384 KB Output is correct
55 Correct 3 ms 4380 KB Output is correct
56 Correct 4 ms 4380 KB Output is correct
57 Correct 4 ms 4308 KB Output is correct
58 Execution timed out 1076 ms 12684 KB Time limit exceeded
59 Halted 0 ms 0 KB -