Submission #1213332

---

Source Code Expand

#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define SZ(X) ((int64_t)((X).size()))
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
#define doublemax (std::numeric_limits<double>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);


uint popcnt(uint x) {
	x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
	x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
	x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);

	x *= 0x0101010101010101ULL;

	return x;
}

int solve(vector<int>a, int pos, int leftmax, int K) {
	//建物の現在の高さがaで、a[pos]とそれより右について
	//K個以上の建物が見える状態にするための最小金額を返す。

	if (K <= 0)return 0;
	const int remain = a.size() - pos;
	if (remain < K)return intmax;

	if (pos == 0)return solve(a, pos + 1, a[0], K - 1);
	if (a.size()<=pos) {
		assert(0);
	}
	
	//a[pos]を上げなくても見える
	if (leftmax < a[pos]) {
		return solve(a, pos + 1, a[pos], K - 1);
	}
	//上げないと見えない
	int ans1 = solve(a, pos + 1, leftmax, K);
	int cost = leftmax + 1 - a[pos];
	a[pos] = leftmax + 1;
	int ans2 = cost + solve(a, pos + 1, a[pos], K - 1);
	return min(ans1, ans2);
}


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;
	vector<int>a(N);
	rep(i, N)cin >> a[i];

	int ans = solve(a, 0, 0, K);
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result