oj.uz

Submission #709873

# Submission time Handle Problem Language Result Execution time Memory
709873 2023-03-14T18:28:28 Z mariaclara Kronican (COCI16_kronican) C++17
100 / 100
 675 ms 8532 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, k, dp[(1<<21)], dist[25][25];

int bitcont(int x) {
   int cont = 0;
   while(x!=0) {
      x-=x&-x;
      cont++;
   }
   return cont;
}

int bitmask(int mask) {
   //cout << "--------\n" << mask << ":\n";
   if(bitcont(mask)==n-k) return 0;
   if(dp[mask]!=-1) return dp[mask];

   int resp = 1e9;
   for(int i = 0; i < n; i++) {
      if((1<<i)&mask) continue;
      int at = 1e9;
      for(int j = 0; j < n; j++)
         if(!((1<<j)&mask) and i!=j) at = min(at, dist[i][j]);

      //cout << "Volta mask " << mask << ": " << at << " " << i << "\n";
      resp = min(resp, at+bitmask(mask+(1<<i)));
   }

   return dp[mask] = resp;
}
int main () {
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin >> n >> k;

   for(int i = 0; i < n; i++)
      for(int j = 0; j < n; j++)
         cin >> dist[i][j];

   memset(dp, -1, sizeof(dp));

   cout << bitmask(0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 3 ms 8520 KB Output is correct
3 Correct 4 ms 8532 KB Output is correct
4 Correct 5 ms 8532 KB Output is correct
5 Correct 9 ms 8532 KB Output is correct
6 Correct 18 ms 8524 KB Output is correct
7 Correct 27 ms 8532 KB Output is correct
8 Correct 56 ms 8512 KB Output is correct
9 Correct 675 ms 8532 KB Output is correct
10 Correct 51 ms 8404 KB Output is correct