Submission #896853

#	Time	Username	Problem	Language	Result	Execution time	Memory
896853		mihtriii295	Kronican (COCI16_kronican)	C++17	100 / 100	269 ms	16980 KiB

kronican

#include<bits/stdc++.h>

#define ll  long long

#define el  cout << '\n' 

using namespace std;

const ll N = 21;
const ll logN = 20;
const ll MOD = 1e9 + 7;

int n, m;
ll f[1 << N], res = 1e9, a[21][21], k;
int main(){
    if(fopen("coci1617_r3_kronican.inp", "r")){
        freopen("coci1617_r3_kronican.inp", "r", stdin);
        freopen("coci1617_r3_kronican.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cout.tie(NULL);
    memset(f, 32, sizeof f);
    cin >> n >> k;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];
    }
    f[(1 << n) - 1] = 0;
    for (int mask = (1 << n) - 1; mask >= 0; --mask){
        for (int biti = mask; biti > 0; biti -= biti & -biti){
            int i = 31 - __builtin_clz(biti & - biti);
            for (int bitj = mask; bitj > 0; bitj -= bitj & -bitj){
                int j = 31 - __builtin_clz(bitj & - bitj); 
                if (i == j) continue;
                f[mask ^ (1 << i)] = min(f[mask ^ (1 << i)], f[mask] + a[i][j]);
            }
        }
    }
    for (int i = 0; i < (1 << n); ++i)
        if (__builtin_popcount(i) <= k){
            res = min(res, f[i]);
        }
    cout << res;
    return 0;
}

Compilation message (stderr)

kronican.cpp: In function 'int main()':
kronican.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen("coci1617_r3_kronican.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kronican.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("coci1617_r3_kronican.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100