oj.uz

답안 #1042148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042148 2024-08-02T15:22:30 Z biserailieva Kronican (COCI16_kronican) C++14
100 / 100
 438 ms 8636 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
 
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n, k; cin >> n >> k;
	int d[n][n];
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			cin >> d[i][j];
	const int LIM = 1<<n;
	int dp[LIM];
	dp[0] = 0;
	int ans = 1e18;
	if(k==n){
		cout << 0;
		return 0;
	}
	for(int i=1; i<LIM; ++i){
		dp[i] = 1e18;
		int cnt = 0;
		for(int j=0; j<n; ++j){
			if(!((1<<j)&i)){
				++cnt;
				continue;
			}
			for(int l=0; l<n; ++l){
				if(((1<<l)&i)) continue;
				dp[i] = min(dp[i], dp[i^(1<<j)] + d[j][l]);
			}
		}
		if(cnt==k) ans = min(ans, dp[i]);
	}
	cout << ans;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 10 ms 708 KB Output is correct
7 Correct 20 ms 968 KB Output is correct
8 Correct 59 ms 1376 KB Output is correct
9 Correct 432 ms 8636 KB Output is correct
10 Correct 438 ms 8540 KB Output is correct