Submission #1268403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268403		haithamcoder	Kronican (COCI16_kronican)	C++20	100 / 100	700 ms	8520 KiB

kronican

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

typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 1000000007;
const ll LOG = 31, inf = 1e17;

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);


int main() {
    Algerian OI

    ll n, k;
    cin >> n >> k;
    vector<vector<ll>> c(n, vector<ll>(n));

    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) cin >> c[i][j];
    }

    vector<ll> dp(1 << n, inf);

    // dbg(__builtin_popcount(7));


    for (ll mask = 0; mask < (1 << n); mask++) {
        if (__builtin_popcount(mask) == k) {
            dp[mask] = 0;
            continue;
        } else if (__builtin_popcount(mask) < k) continue;

        for (ll i = 0; i < n; i++) {
            ll mn = inf;
            if (!((mask >> i) & 1)) continue;
            for (ll j = 0; j < n; j++) {
                if (j == i || !((mask >> j) & 1)) continue;

                mn = min(mn, c[i][j]);
            }

            dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + mn);
        }
    }

    cout << dp[(1 << n) - 1] << "\n";
    return 0;
}

• Subtask 1: 100 / 100