Submission #584609

#	Time	Username	Problem	Language	Result	Execution time	Memory
584609		HeyYouNotYouYou	Kronican (COCI16_kronican)	C++14	90 / 100	2081 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 count(int n){
	int cnt=0;
	while(n){
		cnt++;
		n>>=1;
	}
	return cnt;
}
int solve(int mask){
	if(count(mask)-__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);
	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));
}

• Subtask 1: 90 / 100