oj.uz

Submission #98537

# Submission time Handle Problem Language Result Execution time Memory
98537 2019-02-23T21:47:53 Z pamaj Kronican (COCI16_kronican) C++17
0 / 100
 1355 ms 17016 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
#define int uint_fast32_t

#pragma GCC optimize ("Ofast")

int n, k;
int c[maxn][maxn];
int dp[1 << 20];

int32_t main()
{	
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> k;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
			cin >> c[i][j];
	}


	for(int mask = (1 << n) - 1; mask >= 0; mask--)
	{
		if(__builtin_popcount(mask) >= n - k) {dp[mask] = 0; continue;}

		int ans = 1e7;

		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(i == j or (mask & (1 << i)) or (mask & (1 << j))) continue;

				ans = min(ans, dp[mask ^ (1 << i)] + c[i][j]);
			}
		}

		dp[mask] = ans;
	}

	cout << dp[0] << "\n";
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 26 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 44 ms 1528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 102 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1355 ms 16920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 102 ms 17016 KB Execution killed with signal 11 (could be triggered by violating memory limits)