oj.uz

Submission #584615

# Submission time Handle Problem Language Result Execution time Memory
584615 2022-06-27T16:26:43 Z HeyYouNotYouYou Kronican (COCI16_kronican) C++14
100 / 100
 1678 ms 16724 KB 
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int dp[1<<21];
int n , k ;
int arr[21][21];
int solve(int mask){
	if(__builtin_popcount(mask)==k) return 0;
	if(dp[mask]!=-1) return dp[mask];
	int cur = INT_MAX;
	for(int i = 0 ; i < n ; i ++)
	for(int j = 0 ; j < n ; j++){
		if(i==j) continue;
		if(!((1<<j)&mask)||!((1<<i)&mask)) continue;
		cur =  min(cur, solve(mask^(1<<i))+arr[i][j]);
	}
	dp[mask] = cur;
	return dp[mask];
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16724 KB Output is correct
2 Correct 6 ms 16724 KB Output is correct
3 Correct 6 ms 16724 KB Output is correct
4 Correct 7 ms 16724 KB Output is correct
5 Correct 18 ms 16724 KB Output is correct
6 Correct 35 ms 16724 KB Output is correct
7 Correct 56 ms 16724 KB Output is correct
8 Correct 124 ms 16724 KB Output is correct
9 Correct 1678 ms 16724 KB Output is correct
10 Correct 111 ms 16724 KB Output is correct