Submission #1174526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174526		Nomio	Kronican (COCI16_kronican)	C++20	100 / 100	612 ms	8520 KiB

kronican

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	int c[n][n];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			cin >> c[i][j];
		}
	}
	vector<ll> dp((1 << n), 1e18);
	ll ans = 1e18;
	dp[(1 << n) - 1] = 0;
	for(int a = (1 << n) - 1; a >= 0; a--) {
		for(int i = 0; i < n; i++) {
			if((a >> i) % 2 == 1) {
				for(int j = 0; j < n; j++) {
					if(i == j) continue;
					if((a >> j) % 2 == 1) {
						int b = a - (1 << i);
						dp[b] = min(dp[b], dp[a] + c[i][j]);
					}
				}
			}
		}
	}
	for(int i = 0; i < (1 << n); i++) {
		int K = 0;
		for(int j = 0; j < n; j++) {
			if((i >> j) % 2 == 1) K++;
		}
		if(K <= k) ans = min(ans, dp[i]);
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 100 / 100