oj.uz

Submission #638396

# Submission time Handle Problem Language Result Execution time Memory
638396 2022-09-05T19:08:53 Z NeroZein Kronican (COCI16_kronican) C++14
100 / 100
 651 ms 4396 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

const int N = 20; 
int n,k,a[N][N],best[1<<N];

using namespace std;

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>k;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    }
    int ans = 1e9;
    for(int mask=(1<<n)-2;mask>=0;mask--){
        best[mask] = 1e9;
        for(int i=0;i<n;i++){
            if ((mask&(1<<i)) == 0)continue;
            for(int j=0;j<n;j++){
                if ((mask&(1<<j)) == 1)continue;
                best[mask] = min(best[mask],best[mask|(1<<j)]+a[j][i]);
            }
        }
        if (__builtin_popcount(mask) == k)
            ans = min(ans, best[mask]);
    }cout<<ans;

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 12 ms 440 KB Output is correct
7 Correct 26 ms 468 KB Output is correct
8 Correct 56 ms 760 KB Output is correct
9 Correct 651 ms 4332 KB Output is correct
10 Correct 634 ms 4396 KB Output is correct