Submission #443550

#	Time	Username	Problem	Language	Result	Execution time	Memory
443550		penguinhacker	Kronican (COCI16_kronican)	C++14	100 / 100	816 ms	4420 KiB

kronican

#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 / 100