제출 #243431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243431		VEGAnn	Kronican (COCI16_kronican)	C++14	100 / 100	746 ms	4576 KiB

kronican

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;
const int N = 20;
const int oo = 2e9;
int a[N][N], ans = oo, n, k, f[(1 << N)];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

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

    fill(f, f + (1 << n), oo);

    f[(1 << n) - 1] = 0;

    for (int msk = (1 << n) - 1; msk > 0; msk--)
        if (__builtin_popcount(msk) <= k){
            ans = min(ans, f[msk]);
        } else {
            for (int fr = 0; fr < n; fr++)
                if (msk & (1 << fr)){
                    int nw = (msk ^ (1 << fr));

                    for (int wh = 0; wh < n; wh++)
                        if (nw & (1 << wh))
                            f[nw] = min(f[nw], f[msk] + a[fr][wh]);
                }
        }

    cout << ans;

    return 0;
}

• Subtask 1: 100 / 100