제출 #244197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244197		NONAME	Kronican (COCI16_kronican)	C++14	100 / 100	1100 ms	4600 KiB

kronican

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

int n, k, f[(1 << 20)], ans = -1, a[20][20];

int main() {
    fast_io;

    cin >> n >> k;

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

    for (int i = 0; i < (1 << n); ++i)
        f[i] = -1;

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

    for (int msk = (1 << n) - 1; msk >= 0; --msk) {
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;

            if (!(msk & (1 << i)))
                continue;

            if (!(msk & (1 << j)))
                continue;

            int nmsk = msk ^ (1 << i);

            f[nmsk] = (f[nmsk] == -1 ? f[msk] + a[i][j] : min(f[nmsk], f[msk] + a[i][j]));
        }
    }

    //for (int i = 0; i < (1 << n); ++i)
        //cerr << __builtin_popcount(i) << " " << i << " " << f[i] << "\n";

    for (int i = 0; i < (1 << n); ++i)
        if (__builtin_popcount(i) == k)
            ans = (ans == -1 ? f[i] : min(ans, f[i]));

    cout << ans << "\n";
}

• Subtask 1: 100 / 100