Submission #345188

#	Time	Username	Problem	Language	Result	Execution time	Memory
345188		l3nl3	K blocks (IZhO14_blocks)	C++14	32 / 100	152 ms	512 KiB

blocks

#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, st[mxsz][21], lgg[mxsz+7];

int get (int l, int r) {
	int j = lgg[r-l+1];
	return max(st[l][j], st[r - (1 << j) + 1][j]);
}

signed main () { ioio();
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	lgg[1] = 0;
	for (int i = 2; i <= n; i++) {
		lgg[i] = lgg[i>>1] + 1;
	}
	for (int i = 0; i < n; i++)
	    st[i][0] = a[i];
	for (int j = 1; j <= 20; j++)
	    for (int i = 0; i + (1 << j) <= n; i++)
	        st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
	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);
				}
			}
			if (po.size() == k-1) {
				po.push_back(n-1);
				int sm = 0;
				sm += get(0, po[0]);
				for (int i = 1; i < po.size(); i++) {
					sm += get(po[i-1] + 1, po[i]);
				}
				mn = min (mn, sm);
			}
		}
		cout << mn;
		exit;
	} else if (k <= 5) {
		n--;
		if (k == 1) {
			cout << get (0, n);
			exit;
		}
		if (k == 2) {
			for (int a = 1; a <= n; a++) {
				if (a == 1) {
					mn = get (0, a-1) + get (a, n);
					continue;
				}
				mn = min (mn, get (0, a-1) + get (a, n));
			}
			cout << mn;
			exit;
		}
		if (k == 3) {
			for (int a = 1; a <= n-1; a++) {
				for (int b = a+1; b <= n; b++) {
					if (a == 1 && b == 2) {
						mn = get (0, a-1) + get (a, b-1) + get (b, n);
						continue;
					}
					mn = min (mn, get (0, a-1) + get (a, b-1) + get (b, n));
				}
			}
			cout << mn;
			exit;
		}
		if (k == 4) {
			for (int a = 1; a <= n-2; a++) {
				for (int b = a+1; b <= n-1; b++) {
					for (int c = b+1; c <= n; c++) {
						if (a == 1 && b == 2 && c == 3) {
							mn = get (0, a-1) + get (a, b-1) + get (b, c-1) + get (c, n);
							continue;
						}
						mn = min (mn, get (0, a-1) + get (a, b-1) + get (b, c-1) + get (c, n));
					}
				}	
			}
			cout << mn;
			exit;
		}
		if (k == 5) {
			for (int a = 1; a <= n-3; a++) {
				for (int b = a+1; b <= n-2; b++) {
					for (int c = b+1; c <= n-1; c++) {
						for (int d = c+1; d <= n; d++) {
							if (a == 1 && b == 2 && c == 3 && d == 4) {
								mn = get (0, a-1) + get (a, b-1) + get (b, c-1) + get (c, d-1) + get (d, n);
								continue;
							}
							mn = min (mn, get (0, a-1) + get (a, b-1) + get (b, c-1) + get (c, d-1) + get (d, n));
						}
					}
				}
			}
			cout << mn;
			exit;
		}
	}
	else {
		cout << "wronganswer";
	}
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:54: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]
   54 |    if (po.size() == k-1) {
      |        ~~~~~~~~~~^~~~~~
blocks.cpp:58: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]
   58 |     for (int i = 1; i < po.size(); i++) {
      |                     ~~^~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47