Submission #84686

#	Time	Username	Problem	Language	Result	Execution time	Memory
84686		luciocf	Kronican (COCI16_kronican)	C++14	30 / 100	7 ms	1860 KiB

kronican

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 11;
 
const int inf = 1e9+10;
 
typedef pair<int, int> pii;
 
int num[maxn][maxn], n, k;
 	
int dp[1<<10][maxn][maxn];
 
int solve(int mask, int pos, int qtd)
{
	if (__builtin_popcount(mask) == k) return 0;
	if (qtd == n) return inf;
	if (dp[mask][pos][qtd] != -1) return dp[mask][pos][qtd];
 
	int caso1 = inf;
	for (int i = 0; i < n; i++)
		if (i != pos && (mask&(1<<i)))
			caso1 = min(caso1, solve(mask, i, qtd+1));
 
	if (!(mask&(1<<pos))) return dp[mask][pos][qtd] = caso1;
 
	int caso2 = inf;
	for (int i = 0; i < n; i++)
		if (i != pos && (mask&(1<<i)))
			caso2 = min(caso2, num[pos][i]+solve(mask^(1<<pos), i, qtd+1));
 
	return dp[mask][pos][qtd] = min(caso1, caso2);
}
 
int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> num[i][j];
 
	memset(dp, -1, sizeof dp);
 
	cout << solve((1<<n)-1, 0, 0) << "\n";
}

• Subtask 1: 30 / 100