Submission #1213239

---

Source Code Expand

//見えてほしい建物を決め打ちO(2^n)したとき, 左の建物から高さを決めていくことができる。
//左から見る。最初の建物はその高さがよい。見える建物について、高さをhにしてよいのならh以下にすべき。
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

int n, k;
int a[15];
int ma[15];

signed main() {
	int i, j, l;
	
	cin >> n >> k;
	if (k <= 1) { cout << 0 << endl; return 0; }
	for (i = 0; i < n; i++) cin >> a[i];
	ma[0] = a[0];
	for (i = 1; i < n; i++) ma[i] = max(a[i], ma[i - 1]);
	
	int ans = 1145141919810;
	
	for (i = 0; i < (1 << n); i++) {
		vector<int> ids;
		
		for (j = 0; j < n; j++) {
			if ((i >> j) % 2) {
				ids.push_back(j);
			}
		}
		if (ids.size() < k) { continue; }
		
		int maxHigh = 0;
		int sumCost = 0;
		for (j = 0; j < ids.size(); j++) {
			int high = max(ma[ids[j]], maxHigh + 1);
			maxHigh = high;
			sumCost += high - a[ids[j]];
		}
		ans = min(ans, sumCost);
	}
	
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result