oj.uz

Submission #387997

# Submission time Handle Problem Language Result Execution time Memory
387997 2021-04-09T16:50:43 Z tushar_2658 Kronican (COCI16_kronican) C++14
100 / 100
 1903 ms 9552 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 11 ms 488 KB Output is correct
6 Correct 28 ms 588 KB Output is correct
7 Correct 53 ms 844 KB Output is correct
8 Correct 125 ms 1488 KB Output is correct
9 Correct 1903 ms 9552 KB Output is correct
10 Correct 145 ms 7220 KB Output is correct