fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 1e6 + 5;
  5. //
  6. int n, T;
  7. unordered_map<int, int> mp;
  8. bitset<mx> dp(1);
  9. //
  10. void process (void)
  11. {
  12.     cin >> n >> T;
  13.     for (int w; n--;)
  14.         cin >> w,
  15.         ++mp[w];
  16.  
  17.     for (auto [w, cnt] : mp)
  18.     {
  19.         int p;
  20.         //
  21.         for (p = 0; (1 << p + 1) - 1 <= cnt; ++p)
  22.             if ((1LL << p) * w <= T)
  23.                 dp |= dp << (1 << p) * w;
  24.         if (cnt > (1LL << p) - 1 && (cnt - (1 << p) + 1) * w <= T)
  25.             dp |= dp << (cnt - (1 << p) + 1) * w;
  26.     }
  27.  
  28.     for (int i = 1; i <= T; ++i)
  29.         cout << dp[i];
  30. }
  31. //
  32. signed main (void)
  33. {
  34.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  35.     process();
  36. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TG1qGL
https://m...content-available-to-author-only...j.com/problem/554
language:
C++14 (gcc 8.3)
created:
2 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!