oj.uz

Submission #735663

# Submission time Handle Problem Language Result Execution time Memory
735663 2023-05-04T12:42:05 Z Nhoksocqt1 Kronican (COCI16_kronican) C++17
100 / 100
 273 ms 4432 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
typedef long long ll;

const int N = 20;
int C[N][N], f[(1 << N) + 5], k, n;

void process() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> C[i][j];
        }
    }

    if(n == k) {
        cout << 0;
        return;
    }

    memset(f, 0x3f, sizeof(f));
    for (int mask = 0; mask < (1 << n); ++mask) {
        if(__builtin_popcount(mask) <= k) {
            f[mask] = 0;
        }
    }

    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i1 = mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1);
            for (int j1 = ((1 << n) - 1) ^ mask; j1 > 0; j1 ^= j1 & -j1) {
                int j = __builtin_ctz(j1 & -j1);
                f[mask | (1 << j)] = min(f[mask | (1 << j)], f[mask] + C[j][i]);
            }
        }
    }

    cout << f[(1 << n) - 1];
}

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

	process();
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 3 ms 4428 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 6 ms 4308 KB Output is correct
6 Correct 10 ms 4308 KB Output is correct
7 Correct 18 ms 4432 KB Output is correct
8 Correct 25 ms 4308 KB Output is correct
9 Correct 256 ms 4416 KB Output is correct
10 Correct 273 ms 4308 KB Output is correct