Submission #584615

#	Time	Username	Problem	Language	Result	Execution time	Memory
584615		HeyYouNotYouYou	Kronican (COCI16_kronican)	C++14	100 / 100	1678 ms	16724 KiB

kronican

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int dp[1<<21];
int n , k ;
int arr[21][21];
int solve(int mask){
	if(__builtin_popcount(mask)==k) return 0;
	if(dp[mask]!=-1) return dp[mask];
	int cur = INT_MAX;
	for(int i = 0 ; i < n ; i ++)
	for(int j = 0 ; j < n ; j++){
		if(i==j) continue;
		if(!((1<<j)&mask)||!((1<<i)&mask)) continue;
		cur =  min(cur, solve(mask^(1<<i))+arr[i][j]);
	}
	dp[mask] = cur;
	return dp[mask];
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < n ; j ++)
		{
			cin>>arr[i][j];
		}
	}
	memset(dp,-1,sizeof dp);
	cout<<solve((1<<n)-1);
}

• Subtask 1: 100 / 100