oj.uz

Submission #443550

# Submission time Handle Problem Language Result Execution time Memory
443550 2021-07-10T18:08:42 Z penguinhacker Kronican (COCI16_kronican) C++14
100 / 100
 816 ms 4420 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, k, c[20][20], dp[1<<20];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=0; i<n; ++i)
		for (int j=0; j<n; ++j)
			cin >> c[i][j];
	memset(dp, 0x3f, sizeof(dp));
	dp[(1<<n)-1]=0;
	int ans=69696969;
	for (int i=(1<<n)-1; i; --i) {
		int x=__builtin_popcount(i);
		if (x<k)
			continue;
		if (x==k) {
			ans=min(ans, dp[i]);
			continue;
		}
		for (int j=0; j<n; ++j)
			if (i&1<<j)
				for (int k2=0; k2<n; ++k2)
					if (j^k2&&i&1<<k2)
						dp[i^1<<j]=min(dp[i^1<<j], dp[i]+c[j][k2]);
	}
	cout << ans;
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4300 KB Output is correct
2 Correct 2 ms 4420 KB Output is correct
3 Correct 2 ms 4300 KB Output is correct
4 Correct 3 ms 4300 KB Output is correct
5 Correct 9 ms 4416 KB Output is correct
6 Correct 18 ms 4412 KB Output is correct
7 Correct 33 ms 4300 KB Output is correct
8 Correct 74 ms 4300 KB Output is correct
9 Correct 816 ms 4400 KB Output is correct
10 Correct 66 ms 4400 KB Output is correct