oj.uz

Submission #84686

# Submission time Handle Problem Language Result Execution time Memory
84686 2018-11-16T14:02:46 Z luciocf Kronican (COCI16_kronican) C++14
30 / 100
 7 ms 1860 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)
{
	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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 3 ms 1012 KB Output is correct
3 Correct 4 ms 1012 KB Output is correct
4 Incorrect 7 ms 1012 KB Output isn't correct
5 Runtime error 3 ms 1636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 1776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 1776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 1776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 1776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 1860 KB Execution killed with signal 11 (could be triggered by violating memory limits)