oj.uz

Submission #676502

# Submission time Handle Problem Language Result Execution time Memory
676502 2022-12-31T03:51:07 Z penguin133 Kronican (COCI16_kronican) C++17
100 / 100
 479 ms 8588 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int A[25][25], ans = 1e18, dp[(1<<20) + 1];
main(){
	int n,k;
	cin >> n >> k;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin >> A[i][j];
	for(int i=(1<<n)-2;i>=0;i--){
		dp[i] = 1e18;
		int cnt =0;
		for(int j=0;j<n;j++){
			if(!(i >> j & 1)){
				int mini = 1e9;
				for(int x=0;x<n;x++){
					if(i >> x & 1)mini = min(mini, A[j][x]);
				}
				dp[i] = min(dp[i], dp[i+(1<<j)] + mini);
				
			}
			else cnt++;
		}
		if(cnt <= k)ans = min(ans, dp[i]);
	}
	cout << (n == k ? 0 : ans);
}

Compilation message

kronican.cpp:5:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    5 | main(){
      | ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 11 ms 460 KB Output is correct
7 Correct 24 ms 788 KB Output is correct
8 Correct 49 ms 1260 KB Output is correct
9 Correct 474 ms 8532 KB Output is correct
10 Correct 479 ms 8588 KB Output is correct