oj.uz

Submission #934498

# Submission time Handle Problem Language Result Execution time Memory
934498 2024-02-27T13:09:30 Z TIN Kronican (COCI16_kronican) C++17
100 / 100
 554 ms 4436 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 12 ms 484 KB Output is correct
7 Correct 23 ms 2652 KB Output is correct
8 Correct 51 ms 2512 KB Output is correct
9 Correct 554 ms 4436 KB Output is correct
10 Correct 60 ms 4436 KB Output is correct