제출 #1273857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273857		flaming_top1	Kronican (COCI16_kronican)	C++20	100 / 100	472 ms	4868 KiB

kronican

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int n, k;
int a[25][25], dp[(1 << 20) + 5];

fami lore()
{
    SPED;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    memset(dp, 0x1f, sizeof dp);
    for (int mask = 1; mask < (1 << n); mask++)
    {
        if (__builtin_popcountll(mask) < k)
            continue;
        else if (__builtin_popcountll(mask) == k)
            dp[mask] = 0;

        for (int i = 0; i < n; i++)
            if (mask >> i & 1)
                for (int j = 0; j < n; j++)
                    if (!(mask >> j & 1))
                        dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + a[j][i]);
    }
    cout << dp[(1 << n) - 1];
}
// Let your soul wander where dreams are born.

• Subtask 1: 100 / 100