제출 #1021295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021295		ZeroCool	Kronican (COCI16_kronican)	C++14	100 / 100	562 ms	8640 KiB

kronican

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array
#define int long long

const int N = 20;
const int INF = 1e17;
const int X = 1e5 + 20;

#pragma GCC optimize("unroll-loops,O2,Ofast,O3")
#pragma GCC target("avx2")

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n, k;
	cin>>n>>k;
	int A[n][n];
	for(int i  =0; i < n;i++){
		for(int j = 0;j < n;j++){
			cin>>A[i][j];
		}
	}
	
	int dp[(1 << n)];
	for(int i = 0;i < (1 << n);i++)dp[i] = INF;
	dp[(1 << n) - 1] = 0;
	int ans = INF;
	for(int msk = (1 << n) - 1;msk >= 0;msk--){
		if(__builtin_popcount(msk) <= k){
			ans = min(ans, dp[msk]);
			continue;
		}
		for(int j = 0;j < n;j++){
			if((1 << j) & msk){
				for(int k = 0;k < n;k++){
					if(j == k)continue;
					if((1 << k) & msk){
						dp[msk ^ (1 << j)] = min(dp[msk ^ (1 << j)], dp[msk] + A[j][k]);
					}
				}
			}

		}
	}
	cout<<ans;
}

• Subtask 1: 100 / 100