제출 #1123683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123683		votranngocvy	Kronican (COCI16_kronican)	C++20	100 / 100	549 ms	8648 KiB

kronican

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

#define int long long
const int M = (1 << 20) + 5;
const int inf = 1e18;
int a[25][25],dp[M];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];
    for (int mask = 0; mask < (1 << n); mask++) dp[mask] = inf;
    dp[(1 << n) - 1] = 0;
    int ans = inf;
    for (int mask = (1 << n) - 1; mask > 0; mask--) {
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) {
                for (int j = 0; j < n; j++)
                    if (j != i && (mask >> j & 1)) dp[mask ^ (1 << i)] = min(dp[mask ^ (1 << i)],dp[mask] + a[i][j]);
            }
        if (__builtin_popcount(mask) <= k) ans = min(ans,dp[mask]);
    }
    cout << ans << "\n";
}

• Subtask 1: 100 / 100