oj.uz

Submission #84683

# Submission time Handle Problem Language Result Execution time Memory
84683 2018-11-16T14:00:42 Z luciocf Kronican (COCI16_kronican) C++14
0 / 100
 46 ms 12280 KB 
#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)
{
	int on = 0;
	for (int i = 0; i < n; i++)
		if (mask&(1<<i)) on++;
 
	if (on == k)
	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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 12280 KB Output isn't correct
2 Incorrect 46 ms 12280 KB Output isn't correct
3 Incorrect 38 ms 12280 KB Output isn't correct
4 Incorrect 11 ms 12280 KB Output isn't correct
5 Runtime error 3 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 7 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 4 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)