oj.uz

Submission #391660

# Submission time Handle Problem Language Result Execution time Memory
391660 2021-04-19T13:14:20 Z saarang123 K blocks (IZhO14_blocks) C++17
53 / 100
 1000 ms 1484 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxn = 100 * 1000 + 3, mxk = 103;
int dp[mxk][mxn], a[mxn];
int n, k;

template<class T> struct SparseTable { // comb(ID,b) = b
    T ID = T();
    function<T(const T&,const T&)> comb;
    int n, k; vector<vector<T>> seg;
    void init(int _n, T base, function<T(const T&,const T&)> join) {
        n = _n; k = lg(n); comb = join; ID = base; seg.assign(_n + 1, vector<T> (k + 1, ID)); }
    int lg(int x) { return 31 - __builtin_clz(x); }   //CHECK THIS
    void build() {
        for(int i = 1; i <= n; i++) seg[i][0] = a[i];
        for(int j = 1; j <= k; j++)
            for(int i = 1; i + (1 << j) - 1 <= n; i++)
                seg[i][j] = comb(seg[i][j - 1], seg[i + (1 << (j - 1))][j - 1]);
    }
    T query(int L, int R) {
        int j = lg(R - L + 1);
        return comb(seg[L][j], seg[R - (1 << j) + 1][j]);
    }
};

SparseTable<int> st;

// void f(int i, int l, int r, int optl, int optr) {
// 	if(l > r)
// 		return;
// 	int mid = (l + r) >> 1, opt = -1;
// 	dp[i][mid] = 1e9;
// 	for(int m = optl; m < min(optr, mid); m++) {
// 		int cost = st.query(m + 1, mid);
// 		if(dp[i][mid] > dp[i - 1][m] + cost) {
// 			dp[i][mid] = dp[i - 1][m] + cost;
// 			opt = m;
// 		}
// 	}
// 	cout << opt << '\n';
// 	f(i, l, mid - 1, optl, opt);
// 	f(i, mid + 1, r, opt, optr);
// }

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    	dp[0][i] = 1e9;
    }
    st.init(n, 0, [&] (int x, int y) {
    	return max(x, y);
    });
    st.build();
    // for(int i = 1; i <= k; i++)
    // 	f(i, 1, n, 0, n);
    for(int i = 1; i <= k; i++) {
    	dp[i][0] = 1e9;
    	for(int j = 1; j <= n; j++) {
    		int opt = -1;
    		dp[i][j] = 1e9;
    		for(int l = 0; l < j; l++) {
    			if(dp[i][j] > dp[i - 1][l] + st.query(l + 1, j)) {
    				opt = l + 1;
    				dp[i][j] = dp[i - 1][l] + st.query(l + 1, j);
    			}
    		}
    		//cout << opt << ' ';
    	}
    	//cout << '\n';
    }
    // for(int i = 1; i <= k; i++) {
    // 	for(int j = 1; j <= n; j++)
    // 		cout << dp[i][j] << ' ';
    // 	cout << '\n';
    // }
    cout << dp[k][n] << '\n';
    return 0;
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:67:11: warning: variable 'opt' set but not used [-Wunused-but-set-variable]
   67 |       int opt = -1;
      |           ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 328 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 328 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 3 ms 588 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 1 ms 328 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 1 ms 332 KB Output is correct
45 Correct 1 ms 332 KB Output is correct
46 Correct 1 ms 332 KB Output is correct
47 Correct 1 ms 332 KB Output is correct
48 Correct 1 ms 332 KB Output is correct
49 Correct 1 ms 332 KB Output is correct
50 Correct 1 ms 332 KB Output is correct
51 Correct 2 ms 460 KB Output is correct
52 Correct 2 ms 460 KB Output is correct
53 Correct 5 ms 844 KB Output is correct
54 Correct 6 ms 844 KB Output is correct
55 Correct 3 ms 588 KB Output is correct
56 Correct 4 ms 844 KB Output is correct
57 Correct 5 ms 844 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 304 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 328 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 3 ms 588 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 1 ms 328 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 1 ms 332 KB Output is correct
45 Correct 1 ms 332 KB Output is correct
46 Correct 1 ms 332 KB Output is correct
47 Correct 1 ms 332 KB Output is correct
48 Correct 1 ms 332 KB Output is correct
49 Correct 1 ms 332 KB Output is correct
50 Correct 1 ms 332 KB Output is correct
51 Correct 2 ms 460 KB Output is correct
52 Correct 2 ms 460 KB Output is correct
53 Correct 5 ms 844 KB Output is correct
54 Correct 6 ms 844 KB Output is correct
55 Correct 3 ms 588 KB Output is correct
56 Correct 4 ms 844 KB Output is correct
57 Correct 5 ms 844 KB Output is correct
58 Execution timed out 1099 ms 1484 KB Time limit exceeded
59 Halted 0 ms 0 KB -