oj.uz

Submission #584609

# Submission time Handle Problem Language Result Execution time Memory
584609 2022-06-27T16:22:02 Z HeyYouNotYouYou Kronican (COCI16_kronican) C++14
90 / 100
 2000 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 count(int n){
	int cnt=0;
	while(n){
		cnt++;
		n>>=1;
	}
	return cnt;
}
int solve(int mask){
	if(count(mask)-__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);
	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));
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 9 ms 16648 KB Output is correct
4 Correct 7 ms 16724 KB Output is correct
5 Correct 21 ms 16596 KB Output is correct
6 Correct 45 ms 16700 KB Output is correct
7 Correct 96 ms 16700 KB Output is correct
8 Correct 213 ms 16596 KB Output is correct
9 Execution timed out 2081 ms 16596 KB Time limit exceeded
10 Correct 233 ms 16700 KB Output is correct