fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int adj[12][22][22], dp[12][(1<<20)+5];
  6. int n[12], tong[22];
  7. int l, k, ans = 1e6;
  8.  
  9. int dem(int mask){
  10.     int cnt = 0;
  11.     while (mask){
  12.         cnt++;
  13.         mask = mask&(mask-1);
  14.     }
  15.     return cnt;
  16. }
  17.  
  18. int check(int cl, int mask){
  19.     if (cl > l){
  20.         if (dem(mask) >= k) return 1;
  21.         return 0;
  22.     }
  23.  
  24.     for (int i = 0; i < n[cl]; i++) tong[i] = 0;
  25.     for (int u = 0; u < n[cl-1]; u++){
  26.         if ((mask>>u)&1){
  27.             for (int v = 0; v < n[cl]; v++){
  28.                 tong[v] += adj[cl][u][v];
  29.             }
  30.         }
  31.     }
  32.  
  33.     int nmask = 0;
  34.     for (int i = 0; i < n[cl]; i++){
  35.         if (tong[i] > 0) nmask = nmask|(1<<i);
  36.     }
  37.  
  38.     if (dp[cl][nmask] != -1) return dp[cl][nmask];
  39.     return dp[cl][nmask] = check(cl+1, nmask);
  40. }
  41.  
  42. void solve(){
  43.     for (int i = 1; i <= l; i++){
  44.         for (int j = 0; j <= (1<<n[i]); j++) dp[i][j] = -1;
  45.     }
  46.  
  47.     for (int mask = 1; mask < (1<<n[1]); mask++){
  48.         if (check(2, mask) == 1){
  49.             ans = min(ans, dem(mask));
  50.         }
  51.     }
  52.  
  53.     if (ans == 1e6) cout << "-1\n";
  54.     else cout << ans << '\n';
  55. }
  56.  
  57. int main() {
  58.     ios::sync_with_stdio(0);
  59.     cin.tie(0);
  60.  
  61.     cin >> l >> k;
  62.     for (int i = 1; i <= l; i++) cin >> n[i];
  63.     for (int i = 1; i < l; i++){
  64.         for (int j = 0; j < n[i]; j++){
  65.             for (int d = 0; d < n[i+1]; d++){
  66.                 cin >> adj[i+1][j][d];
  67.             }
  68.         }
  69.     }
  70.  
  71.     solve();
  72. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/joL9tw
language:
C++14 (clang 8.0)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!