제출 #722212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722212		trucmai	Kronican (COCI16_kronican)	C++17	100 / 100	1308 ms	16740 KiB

kronican

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

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

#define check(mask,i)  (mask&(1<<i))
#define choose(mask,i) (mask^(1<<i))

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,k,c[30][30],dp[(1<<21)];

ll f(ll mask){
  if(__builtin_popcount(mask) == k) return 0; 
  ll &res = dp[mask]; 
  if(res != -1) return res; 
  res = INF; 
  for(ll i = 0;i < n;++i){
    if(!check(mask,i)) continue; 
    for(ll j = 0;j < n;++j){
      if(!check(mask,j) || i == j) continue; 
      ll nmask = choose(mask,i); 
      res = min(res,f(nmask) + c[i][j]);
    }
  }
  return res;
}

void solve(){
  cin>>n>>k;
  for(ll i = 0;i < n;++i)
    for(ll j = 0;j < n;++j)
      cin>>c[i][j];
  mset(dp,-1);  
  cout<<f((1<<n) - 1)<<endl;
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  // freopen("i.inp","r",stdin);
  // freopen("o.out","w",stdout);
  ll t = 1; //cin>>t;
  while(t--) solve();
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

• Subtask 1: 100 / 100