oj.uz

Submission #709464

# Submission time Handle Problem Language Result Execution time Memory
709464 2023-03-13T16:07:22 Z TAhmed33 Kronican (COCI16_kronican) C++
100 / 100
 1240 ms 8496 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Correct 4 ms 8404 KB Output is correct
4 Correct 4 ms 8404 KB Output is correct
5 Correct 13 ms 8404 KB Output is correct
6 Correct 26 ms 8404 KB Output is correct
7 Correct 41 ms 8404 KB Output is correct
8 Correct 93 ms 8404 KB Output is correct
9 Correct 1240 ms 8496 KB Output is correct
10 Correct 115 ms 8404 KB Output is correct