oj.uz

Submission #98471

# Submission time Handle Problem Language Result Execution time Memory
98471 2019-02-23T18:28:13 Z wjoao Kronican (COCI16_kronican) C++11
40 / 100
 2000 ms 384 KB 
#include<bits/stdc++.h>
#define maxn 20
#define inf 0x3f3f3f3f
#define maxb (1<<maxn)
using namespace std;

int g[50][50], n, k, pd[maxb];

int solve(int bitmask){
  if(__builtin_popcount(bitmask) == k) return 0;

  int best = inf;
  for(int i = 0; i < n; i++){
    if(!((1<<i)&bitmask)){
      int cost = inf;
      for(int j = 0; j < n; j++){
        if(i==j) continue;
        if(!((1<<j)&bitmask)){
          cost = min(cost, g[i][j]);
        }
      }
      best = min(best, cost + solve(bitmask|(1<<i)));
    }
  }
  return best;
}

int main(){
  scanf(" %d %d", &n, &k);
  k = n-k;

  for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++ ) 
      scanf(" %d", &g[i][j]);

  printf("%d\n", solve(0));
  return 0;
}

Compilation message

kronican.cpp: In function 'int main()':
kronican.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d %d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~
kronican.cpp:34:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %d", &g[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 206 ms 364 KB Output is correct
5 Execution timed out 2033 ms 256 KB Time limit exceeded
6 Execution timed out 2058 ms 256 KB Time limit exceeded
7 Execution timed out 2032 ms 256 KB Time limit exceeded
8 Execution timed out 2056 ms 256 KB Time limit exceeded
9 Execution timed out 2021 ms 256 KB Time limit exceeded
10 Execution timed out 2029 ms 256 KB Time limit exceeded