Submission #1218149

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <bitset>
#include <climits>
#include <cstdio>
#include <vector>

using namespace std;

int main()
{
    int N, K;
    if (scanf("%d%d", &N, &K) < 2) return 0;

    vector<int> a(N);
    for (int i = 0; i < N; i++) if (scanf("%d", &a[i]) < 1) return 0;

    long long ans = LLONG_MAX;
    for (int i = 0; i < (1 << N); i++)
    {
        // 最大で15個の建物
        bitset<15> bs(i);

        if (bs.count() != K) continue;

        // ビットが立っている数がKならば
        long long cost = 0;
        int h = 0;
        for (int i = 0; i < N; i++)
        {
            // 見えていたい建物
            if (bs[i])
            {
                // 史上最高保持
                h = max(a[i], h + 1);

                // コスト足し込み 自分が史上最高ならゼロ
                cost += h - a[i];
            }
            // 史上最高保持
            else h = max(a[i], h);
        }

        // 最小コスト保持
        ans = min(ans, cost);
    }

    printf("%lld\n", ans);
    return 0;
}

Submission Info

Judge Result