oj.uz

Submission #98800

# Submission time Handle Problem Language Result Execution time Memory
98800 2019-02-26T01:56:01 Z sofhiasouza Kronican (COCI16_kronican) C++14
100 / 100
 1759 ms 8576 KB 
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int main()
{
	int n, k, dp[2100000], m[22][22];
	cin >> n >> k;
	k = n - k;
	memset(dp, inf, sizeof dp);
	for(int i = 0 ; i < n ; i++)
	{
		for(int j = 0 ; j < n ; j++)
		{
			cin >> m[i][j];
		}
	}
	int menor = inf;
	dp[0] = 0;
	for(int mask = 0 ; mask < (1 << n+1) ; mask++)
	{
		int cont = 0;
		for(int i = 0 ; i < n ; i++)
		{
			if(mask&(1 << i))
			{
				cont++;
				continue;
			}
			for(int j = 0 ; j < n ; j++)
			{
				if(mask&(1 << j) or j == i) continue;
				dp[mask|(1 << j)] = min(dp[mask|(1 << j)], dp[mask]+m[j][i]);		 
			}
		}
		if(cont >= k) menor = min(menor, dp[mask]);
	}
	cout << menor << endl;
}

Compilation message

kronican.cpp: In function 'int main()':
kronican.cpp:19:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  for(int mask = 0 ; mask < (1 << n+1) ; mask++)
                                  ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8576 KB Output is correct
2 Correct 9 ms 8576 KB Output is correct
3 Correct 11 ms 8576 KB Output is correct
4 Correct 9 ms 8576 KB Output is correct
5 Correct 24 ms 8576 KB Output is correct
6 Correct 43 ms 8576 KB Output is correct
7 Correct 81 ms 8576 KB Output is correct
8 Correct 186 ms 8576 KB Output is correct
9 Correct 1759 ms 8576 KB Output is correct
10 Correct 1747 ms 8568 KB Output is correct