Submission #709873

#	Time	Username	Problem	Language	Result	Execution time	Memory
709873		mariaclara	Kronican (COCI16_kronican)	C++17	100 / 100	675 ms	8532 KiB

kronican

#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 / 100