oj.uz

Submission #380345

# Submission time Handle Problem Language Result Execution time Memory
380345 2021-03-21T05:39:10 Z ritul_kr_singh Kronican (COCI16_kronican) C++17
100 / 100
 671 ms 8576 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
 
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, k; cin >> n >> k;
	int d[n][n];
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			cin >> d[i][j];
	const int LIM = 1<<n;
	int dp[LIM];
	dp[0] = 0;
	int ans = 1e18;
	if(k==n){
		cout << 0;
		return 0;
	}
	for(int i=1; i<LIM; ++i){
		dp[i] = 1e18;
		int cnt = 0;
		for(int j=0; j<n; ++j)
			if(!((1<<j)&i)) ++cnt;
		if(cnt < k) continue;
		for(int j=0; j<n; ++j){
			if(!((1<<j)&i)) continue;
			for(int l=0; l<n; ++l){
				if(((1<<l)&i)) continue;
				dp[i] = min(dp[i], dp[i^(1<<j)] + d[j][l]);
			}
		}
		if(cnt==k) ans = min(ans, dp[i]);
	}
	cout << ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 6 ms 492 KB Output is correct
6 Correct 15 ms 620 KB Output is correct
7 Correct 28 ms 876 KB Output is correct
8 Correct 62 ms 1388 KB Output is correct
9 Correct 671 ms 8556 KB Output is correct
10 Correct 105 ms 8576 KB Output is correct