oj.uz

Submission #345171

# Submission time Handle Problem Language Result Execution time Memory
345171 2021-01-07T05:50:17 Z l3nl3 K blocks (IZhO14_blocks) C++14
18 / 100
 155 ms 512 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>  

#define exit exit(false)

//#define here() cerr << "herewego\n";
#define show(x) cerr << #x << ": " << x << '\n';

#define int long long
//#define double long double

#define all(a) a.begin(), a.end()
#define whole(a, p, q) a+p, a+p+q

#define ioio() ios_base::sync_with_stdio (0); cin.tie (0); cout.tie (0);

using namespace std;

//using namespace __gnu_pbds;   
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;  

const int mxsz = 1e5 + 7;

int n, k, a[mxsz], t[mxsz * 4], mn = LLONG_MAX;

void build (int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = a[tl];
		return;
	}
	int tm = (tl + tr) >> 1;
	int lf = (v << 1);
	int rg = (v << 1 | 1);
	build (lf, tl, tm);
	build (rg, tm+1, tr);
	t[v] = max (t[lf], t[rg]);
}

int get (int v, int tl, int tr, int l, int r) {
	if (l <= tl && tr <= r) {
		return t[v];
	}
	if (tr < l || r < tl) {
		return 0;
	}
	int tm = (tl + tr) >> 1;
	int lf = (v << 1);
	int rg = (v << 1 | 1);
	return max(get (lf, tl, tm, l, r), get (rg, tm+1, tr, l, r));
}

int get (int l, int r) {
	return get (1, 1, n, l, r);
}

signed main () { ioio();
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build (1, 1, n);
//	if (k == 1) {
//		cout << get (1, n);
//		exit;
//	}
	if (n <= 20) {
		for (int ma = 1; ma <= (1 << (n-1)); ma++) {
			vector <int> po;
			for (int i = 0; i < n-1; i++) {
				if ((1 << i) & ma) {
					po.push_back(i+1);
				}
			}
			if (po.size() == k-1) {
				po.push_back(n);
				int sm = 0;
				sm += get(1, po[0]);
				for (int i = 1; i < po.size(); i++) {
					sm += get(po[i-1] + 1, po[i]);
				}
//				cerr << sm << ' ' << po[0] << ' ' << po[1] << '\n';
				mn = min (mn, sm);
			}
		}
		cout << mn;
		exit;
	} else {
		cout << "wronganswer";
	}
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:75:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   75 |    if (po.size() == k-1) {
      |        ~~~~~~~~~~^~~~~~
blocks.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 1; i < po.size(); i++) {
      |                     ~~^~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 153 ms 400 KB Output is correct
15 Correct 155 ms 364 KB Output is correct
16 Correct 121 ms 400 KB Output is correct
17 Correct 155 ms 400 KB Output is correct
18 Correct 151 ms 400 KB Output is correct
19 Correct 118 ms 364 KB Output is correct
20 Correct 116 ms 400 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -