제출 #387997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387997		tushar_2658	Kronican (COCI16_kronican)	C++14	100 / 100	1903 ms	9552 KiB

kronican

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

const int maxn = 21;
using ll = long long;

ll a[maxn][maxn];
ll dp[1 << maxn];
bool vis[1 << maxn];
int n, k;

ll call(int mask){
  if(__builtin_popcount(mask) <= k)return 0;
  if(vis[mask])return dp[mask];
  vis[mask] = 1;
  ll ret = 1e18;
  for(int i = 0; i < n; ++i){
    if((mask >> i) & 1){
      for(int j = 0; j < n; ++j){
        if(i == j)continue;
        if((mask >> j) & 1){
          ret = min(ret, call(mask ^ (1 << i)) + a[i][j]);
        }
      }
    }  
  }
  return dp[mask] = ret;
}

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> k;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      cin >> a[i][j];
    }
  }
  cout << call((1 << n) - 1) << '\n';

  return 0;
}

• Subtask 1: 100 / 100