Submission #934498

#	Time	Username	Problem	Language	Result	Execution time	Memory
934498		TIN	Kronican (COCI16_kronican)	C++17	100 / 100	554 ms	4436 KiB

kronican

#include <bits/stdc++.h>

using namespace std;

#define UREP(i,a,b) for (int i = a; i < b; ++i)
#define DREP(i,a,b) for (int i = a; i > b; --i)

const int INF = 1e9;

int v[25][25];
int dp[(1 << 20) + 10];

int n, k, res = INF;

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen("test.inp","r")) {
		freopen("test.inp","r",stdin);
		freopen("test.out","w",stdout);
	}
}

void Solve() {
	//Your Code
	cin >> n >> k;
	UREP(i, 0, n)
		UREP(j, 0, n)
			cin >> v[i][j];
	dp[(1 << n) - 1] = 0;
	if (k == n) res = 0;
	DREP(mask, (1 << n) - 2, 0) {
		dp[mask] = INF;
		int s = 0;
		UREP(i, 0, n) if (mask & (1 << i)) s++;
		if (s < k) continue;
		UREP(i, 0, n) {
			if (!(mask & (1 << i))) {
				int a = INF;
				UREP(j, 0, n)
					if (mask & (1 << j))
						a = min(a, v[i][j]);
				dp[mask] = min(dp[mask], dp[mask | (1 << i)] + a);
			}
		}
		if (s == k) res = min(res, dp[mask]);
	}
	cout << res << '\n';
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 0;
}

Compilation message (stderr)

kronican.cpp: In function 'void Task()':
kronican.cpp:20:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   freopen("test.inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kronican.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen("test.out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100