oj.uz

Submission #896853

# Submission time Handle Problem Language Result Execution time Memory
896853 2024-01-02T09:53:14 Z mihtriii295 Kronican (COCI16_kronican) C++17
100 / 100
 269 ms 16980 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 5 ms 16728 KB Output is correct
6 Correct 8 ms 16980 KB Output is correct
7 Correct 14 ms 16732 KB Output is correct
8 Correct 28 ms 16732 KB Output is correct
9 Correct 268 ms 16732 KB Output is correct
10 Correct 269 ms 16852 KB Output is correct