fork download
copy 
  1. /**
  2.  
  3.  *    author:  longvu
  4.  *    created: 03/10/22 12:24:27
  5. **/
  6. #include<bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define sz(x) ((int)x.size())
  11. #define all(x) (x).begin(), (x).end()
  12. const int INF = numeric_limits<int>::max();
  13. const int nax = (int)(3001);
  14. const int mod = 1e9 + 7;
  15.  
  16. template<class X, class Y>
  17. bool maximize(X& x, const Y y) {
  18.     if (y > x) {x = y; return true;}
  19.     return false;
  20. }
  21. template<class X, class Y>
  22. bool minimize(X& x, const Y y) {
  23.     if (y < x) {x = y; return true;}
  24.     return false;
  25. }
  26.  
  27. const int base = 1001;
  28. #define IDX(x) (x + base)
  29.  
  30. int a[nax], tr[nax], ans[nax];
  31. int32_t main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(0);
  34.     int n, q;
  35.     cin >> n >> q;
  36.     for (int i = 1; i <= n; ++i) {
  37.         cin >> a[i];
  38.     }
  39.     bitset<nax> dp;
  40.     deque<int> dq = {0};
  41.     while (!dq.empty()) {
  42.         int u = dq.front();
  43.         dq.pop_front();
  44.         for (int i = 1; i <= n; ++i) {
  45.             int need = a[i] - q;
  46.             if (u + need > -base 
  47.                 && u + need < base
  48.                 && !dp[IDX(u + need)]) {
  49.                 dp[IDX(u + need)] = 1;
  50.                 tr[IDX(u + need)] = i;
  51.                 dq.push_back(u + need);
  52.             }
  53.         }
  54.     }
  55.     if (!dp[IDX(0)]) {
  56.         cout << "NO" << '\n';
  57.         return 0;
  58.     }
  59.     cout << "YES" << '\n';
  60.     int v = 0;
  61.     do {
  62.         ans[tr[IDX(v)]]++;
  63.         v -= a[tr[IDX(v)]] - q;
  64.     } while (v);
  65.     for (int i = 1; i <= n; ++i) {
  66.         cout << ans[i] << " ";
  67.     }
  68.     cout << '\n';
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/daXDq2
language:
C++14 (clang 8.0)
created:
13 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!