제출 #638396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638396		NeroZein	Kronican (COCI16_kronican)	C++14	100 / 100	651 ms	4396 KiB

kronican

#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 / 100