s8pc_4_b

WAの嵐

bit探索で1を対象のビルとして左から順に探索するだけ。

1のビルの時しかpre_maxを更新していなかったので

N=3,K=4

a={1, 10000, 2, 3}

のようなテストケースを逃していて大量WA

あと最初はlong longも忘れてた

#include<bits/stdc++.h>

using namespace std;

int n, k;

long long int a[22];

int bit_cnt(int bit){

    int cnt = 0;

    for(;bit;bit&=(bit-1)) cnt++;

    return cnt;

}

int main(){

    cin >> n >> k;

    for(int i=0;i<n;i++) cin >> a[i];

    long long int ans = (1LL<<60LL);

    for(int i=0;i<(1<<n);i++){

        if(bit_cnt(i) < k) continue;

        long long int p = 0;

        long long int pre = a[0];

        for(int j=1;j<n;j++){

            if( (i&(1<<j))){

                if(a[j] <= pre){

                    p += (pre - a[j] + 1);

                    pre = max(pre, a[j]) + 1;

                }

            }

            pre = max(pre, a[j]);

        }

        ans = min(ans, p);

    }

    cout << ans << endl;

   

}