oj.uz

Submission #244197

# Submission time Handle Problem Language Result Execution time Memory
244197 2020-07-02T18:58:26 Z NONAME Kronican (COCI16_kronican) C++14
100 / 100
 1100 ms 4600 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

int n, k, f[(1 << 20)], ans = -1, a[20][20];

int main() {
    fast_io;

    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        cin >> a[i][j];

    for (int i = 0; i < (1 << n); ++i)
        f[i] = -1;

    f[(1 << n) - 1] = 0;

    for (int msk = (1 << n) - 1; msk >= 0; --msk) {
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (i == j)
                continue;

            if (!(msk & (1 << i)))
                continue;

            if (!(msk & (1 << j)))
                continue;

            int nmsk = msk ^ (1 << i);

            f[nmsk] = (f[nmsk] == -1 ? f[msk] + a[i][j] : min(f[nmsk], f[msk] + a[i][j]));
        }
    }

    //for (int i = 0; i < (1 << n); ++i)
        //cerr << __builtin_popcount(i) << " " << i << " " << f[i] << "\n";

    for (int i = 0; i < (1 << n); ++i)
        if (__builtin_popcount(i) == k)
            ans = (ans == -1 ? f[i] : min(ans, f[i]));

    cout << ans << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 15 ms 384 KB Output is correct
6 Correct 28 ms 512 KB Output is correct
7 Correct 57 ms 640 KB Output is correct
8 Correct 121 ms 1016 KB Output is correct
9 Correct 1092 ms 4600 KB Output is correct
10 Correct 1100 ms 4464 KB Output is correct