제출 #1016210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016210		VMaksimoski008	Kronican (COCI16_kronican)	C++17	100 / 100	656 ms	4688 KiB

kronican

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

int dp[1<<20];
int n, k, mat[20][20];

int f(int mask) {
    if(__builtin_popcount(mask) == k) return 0;
    if(dp[mask] != -1) return dp[mask];

    int ans = 1e8;
    for(int i=0; i<n; i++) {
        if((mask & (1 << i)) == 0) continue;
        for(int j=0; j<n; j++) {
            if(i == j) continue;
            if((mask & (1 << j)) == 0) continue;
            ans = min(ans, f(mask^(1<<i)) + mat[i][j]);
        }
    }

    return dp[mask] = ans;
}

signed main() {
    cin >> n >> k;

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) cin >> mat[i][j];
    
    memset(dp, -1, sizeof(dp));
    cout << f( (1 << n) - 1 ) << '\n';
    return 0;
}

• Subtask 1: 100 / 100