제출 #735663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735663		Nhoksocqt1	Kronican (COCI16_kronican)	C++17	100 / 100	273 ms	4432 KiB

kronican

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
typedef long long ll;

const int N = 20;
int C[N][N], f[(1 << N) + 5], k, n;

void process() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> C[i][j];
        }
    }

    if(n == k) {
        cout << 0;
        return;
    }

    memset(f, 0x3f, sizeof(f));
    for (int mask = 0; mask < (1 << n); ++mask) {
        if(__builtin_popcount(mask) <= k) {
            f[mask] = 0;
        }
    }

    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i1 = mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1);
            for (int j1 = ((1 << n) - 1) ^ mask; j1 > 0; j1 ^= j1 & -j1) {
                int j = __builtin_ctz(j1 & -j1);
                f[mask | (1 << j)] = min(f[mask | (1 << j)], f[mask] + C[j][i]);
            }
        }
    }

    cout << f[(1 << n) - 1];
}

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

	process();
	return 0;
}

• Subtask 1: 100 / 100