Submission #709464

#	Time	Username	Problem	Language	Result	Execution time	Memory
709464		TAhmed33	Kronican (COCI16_kronican)	C++98	100 / 100	1240 ms	8496 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
int effort[20][20];
int dp[(1 << 20)] = {};
int ans (int mask) {
	if (__builtin_popcount(mask) == k) return 0;
	int &ret = dp[mask];
	if (ret != -1) return ret;
	vector <int> bits;
	for (int i = 0; i < n; i++) if (mask & (1 << i)) bits.push_back(i);
	int u = 1e9;
	for (int i = 0; i < bits.size(); i++) {
		for (int j = i + 1; j < bits.size(); j++) {
			u = min(u, effort[bits[i]][bits[j]] + ans(mask ^ (1 << bits[i])));
			u = min(u, effort[bits[j]][bits[i]] + ans(mask ^ (1 << bits[j])));
		}
	}
	return ret = u;
}
signed main () {
	memset(dp, -1, sizeof(dp));
	cin >> n >> k;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> effort[i][j];
	cout << ans((1 << n) - 1) << endl;
}

Compilation message (stderr)

kronican.cpp: In function 'long long int ans(long long int)':
kronican.cpp:14:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for (int i = 0; i < bits.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
kronican.cpp:15:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for (int j = i + 1; j < bits.size(); j++) {
      |                       ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100