Submission #1283327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283327		diep38	Kronican (COCI16_kronican)	C++20	100 / 100	929 ms	16072 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,k;
int a[50][50];
ll dp[2000005];
ll bitmask(int x){
	if(__builtin_popcount(x)==k){
		return 0;
	}
	ll val=1e18;
	if(dp[x]!=-1) return dp[x];
	for(int i=0;i<n;++i){
		if((x&(1<<i))){
			for(int j=0;j<n;++j){
				if((x&(1<<j)) && j!=i){
					val=min(val,bitmask(x&(~(1<<j)))+a[j][i]);
				}
			}
		}
	}
	return dp[x]=val;
}
signed main(){

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

• Subtask 1: 100 / 100