fork download
copy 
  1. // Written by Gemini
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int n, k, mx;
  7. vector<int> c;
  8. vector<vector<int>> opts;
  9. int dp[505][505];
  10.  
  11. void get_sums(int i, bitset<250005>& bs) {
  12.     if (i == c.size()) return;
  13.     bs |= (bs << c[i]);
  14.     get_sums(i + 1, bs);
  15. }
  16.  
  17. bool solve(int i, int sum) {
  18.     if (sum > n) return false; 
  19.     if (i == n) return (sum == n); 
  20.  
  21.     if (dp[i][sum] != -1) 
  22.         return dp[i][sum];
  23.  
  24.     bool ok = false;
  25.     for (int m : opts[i]) {
  26.         if (solve(i + 1, sum + m)) {
  27.             ok = true;
  28.             break;
  29.         }
  30.     }
  31.  
  32.     return dp[i][sum] = ok;
  33. }
  34.  
  35. int main() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(NULL);
  38.  
  39.     if (!(cin >> n >> k)) return 0;
  40.     mx = n * k;
  41.  
  42.     opts.resize(n);
  43.     memset(dp, -1, sizeof(dp));
  44.  
  45.     bitset<250005> bs;
  46.  
  47.     for (int i = 0; i < n; i++) {
  48.         int l;
  49.         cin >> l;
  50.  
  51.         c.clear();
  52.         for (int j = 0; j < l; j++) {
  53.             int x;
  54.             cin >> x;
  55.             if (x <= mx) {
  56.                 c.push_back(x);
  57.             }
  58.         }
  59.  
  60.         bs.reset();
  61.         bs[0] = 1; 
  62.  
  63.         get_sums(0, bs);
  64.  
  65.         for (int m = 0; m <= n; m++) {
  66.             if (bs[m * k]) {
  67.                 opts[i].push_back(m);
  68.             }
  69.         }
  70.     }
  71.  
  72.     if (solve(0, 0)) {
  73.         cout << "YES\n";
  74.     } else {
  75.         cout << "NO\n";
  76.     }
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4 5
2 11 4
3 13 7 3
1 12
0
stdout
copy 
YES
https://ideone.com/QTxKef
language:
C++ (gcc 8.3)
created:
2 days 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!