제출 #380345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380345		ritul_kr_singh	Kronican (COCI16_kronican)	C++17	100 / 100	671 ms	8576 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
 
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, k; cin >> n >> k;
	int d[n][n];
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			cin >> d[i][j];
	const int LIM = 1<<n;
	int dp[LIM];
	dp[0] = 0;
	int ans = 1e18;
	if(k==n){
		cout << 0;
		return 0;
	}
	for(int i=1; i<LIM; ++i){
		dp[i] = 1e18;
		int cnt = 0;
		for(int j=0; j<n; ++j)
			if(!((1<<j)&i)) ++cnt;
		if(cnt < k) continue;
		for(int j=0; j<n; ++j){
			if(!((1<<j)&i)) continue;
			for(int l=0; l<n; ++l){
				if(((1<<l)&i)) continue;
				dp[i] = min(dp[i], dp[i^(1<<j)] + d[j][l]);
			}
		}
		if(cnt==k) ans = min(ans, dp[i]);
	}
	cout << ans;
}

• Subtask 1: 100 / 100