Submission #1286769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286769		MinhKien	Kronican (COCI16_kronican)	C++20	80 / 100	151 ms	4544 KiB

kronican

#include <iostream>
#include <vector>

using namespace std;

const int M = (1 << 20) - 1;
const int INF = 1e9;

int n, b, dp[M], d[20][20];
vector <int> on;

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

    cin >> n >> b;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> d[i][j];
        }
    }

    fill_n(dp, M, INF);
    dp[(1 << n) - 1] = 0;

    int ans = INF;
    for (int i = (1 << n) - 1; i >= 1; --i) {
        on.clear();
        for (int j = 0; j < n; ++j) {
            if (i >> j & 1) on.push_back(j);
        }

        for (int j = 0; j < on.size(); ++j) {
            int Min = INF;
            for (int k = 0; k < on.size(); ++k) {
                if (j == k) continue;
                Min = min(Min, d[on[j]][on[k]]);
            }
            dp[i ^ (1 << on[j])] = min(dp[i ^ (1 << on[j])], dp[i] + Min);
        }

        if (__builtin_popcount(i) == b) {
            ans = min(ans, dp[i]);
            if (i == (1 << b) - 1) break;
        }
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 80 / 100