제출 #1342144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1342144		rodddd	Kronican (COCI16_kronican)	C++20	100 / 100	483 ms	4356 KiB

kronican

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9+10;
const int maxn = 21;
const int maxm = (1 << 20);

int n, k;

int d[maxn][maxn];

int dp[maxm];

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

	for(int i=0; i<n; i++){
	    for(int j=0; j<n; j++){
	        cin >> d[i][j];
	    }
	}
	
	dp[0] = 0;
	
	for(int mask=1; mask < (1 << n); mask++){
	    dp[mask] = inf;
	    
	    for(int i=0; i<n; i++){
	        if(!(mask & (1<<i))) continue;
	        int prev = mask ^ (1<<i);
	        if(dp[prev] == inf) continue;
	        
	        int best = inf;
	        for(int v=0; v<n; v++){
	            if(mask & (1 << v)) continue;
	            best = min(best, d[i][v]);
	        }
	        if(best == inf) continue;
	        
	        dp[mask] = min(dp[mask], dp[prev]+best);
	    }
	}
	
    int ans=inf;
    for(int mask=0; mask < (1<<n); mask++){
        if(__builtin_popcount(mask) == (n-k)) {
            ans = min(ans, dp[mask]);
        }
        
    }
    
    cout << ans << "\n";
}

• Subtask 1: 100 / 100