oj.uz

Submission #722212

# Submission time Handle Problem Language Result Execution time Memory
722212 2023-04-11T15:12:16 Z trucmai Kronican (COCI16_kronican) C++17
100 / 100
 1308 ms 16740 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16648 KB Output is correct
3 Correct 9 ms 16620 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 15 ms 16740 KB Output is correct
6 Correct 28 ms 16732 KB Output is correct
7 Correct 51 ms 16724 KB Output is correct
8 Correct 100 ms 16724 KB Output is correct
9 Correct 1308 ms 16724 KB Output is correct
10 Correct 107 ms 16724 KB Output is correct