Advertisement
skimono

sky

Dec 8th, 2023
708
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.71 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. //#pragma GCC optimize("Ofast")
  4. //#pragma GCC optimize("no-stack-protector")
  5. //#pragma GCC optimize("unroll-loops")
  6. //#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  7. //#pragma GCC optimize("fast-math")
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <string>
  12. #include <algorithm>
  13. #include <cmath>
  14. #include <stack>
  15. #include <iomanip>
  16. #include <fstream>
  17. #include <string>
  18. #include <set>
  19. #include <deque>
  20. #include <queue>
  21. #include <map>
  22. #include <bitset>
  23. #include <random>
  24. #include <list>
  25. #include <unordered_map>
  26. #include <unordered_set>
  27. #include <cassert>
  28.  
  29. using namespace std;
  30.  
  31. typedef long long ll;
  32. typedef short sh;
  33. typedef unsigned long long ull;
  34. typedef long double ld;
  35. typedef string str;
  36. //typedef __int128 ultraint;
  37. #define sqrt sqrtl
  38. #define F first
  39. #define S second
  40. #define endl '\n'
  41. #define all(vc666) vc666.begin(), vc666.end()
  42. #define allr(vc666) vc666.rbegin(), vc666.rend()
  43. //#define int long long
  44. #define degug(x) cerr (#x) << " " << (x) << endl;
  45.  
  46. const ll INF = 3e18 + 3;
  47. const ll inf = 1e9 + 3;
  48. const ll ONE = 1, ZERO = 0;
  49. const ll mod = 1e9 + 7;
  50. const ll m1 = 1e9 + 575179;
  51. const ll m2 = 1e9 + 87;
  52. const ll LG = 31;
  53. const ll k = 347;
  54. //const ll k_sqrt = 400;
  55. //const ll p = 106033;
  56. ld EPS = 1e-9;
  57. ld PI = 3.1415926535897932384;
  58. ld phi = (sqrt(5) + 1.0) / 2.0;
  59. mt19937_64 gen(40906);
  60.  
  61. const int N = 1e3 + 10;
  62. const int W = 1e2;
  63. int a[N];
  64. bitset <W> w;
  65. bitset <W> zxc;
  66. int pred[W];
  67.  
  68. void solve() {
  69.     int n, i, j, weight = 0;
  70.     cin >> n;
  71.     for (i = 0; i < n; i++) {
  72.         cin >> a[i];
  73.         weight += a[i];
  74.     }
  75.     if (n <= 20) {
  76.         int N = (1 << n);
  77.         int s1 = 0, s2 = 0, mask;
  78.         for (mask = 0; mask < N; mask++) {
  79.             s1 = 0, s2 = 0;
  80.             for (i = 0; i < n; i++) {
  81.                 if (mask & (ONE << i)) {
  82.                     s1 += a[i];
  83.                 }
  84.                 else {
  85.                     s2 += a[i];
  86.                 }
  87.             }
  88.             if (min(s1, s2) * (int)2 >= max(s1, s2)) {
  89.                 cout << "YES" << endl;
  90.                 for (i = 0; i < n; i++) {
  91.                     if (mask & (ONE << i)) {
  92.                         cout << a[i] << " ";
  93.                     }
  94.                 }
  95.                 return;
  96.             }
  97.         }
  98.         cout << "NO" << endl;
  99.     }
  100.     else if (weight / 3 < W) {
  101.         w[0] = 1;
  102.         for (i = 0; i < n; i++) {
  103.             w |= (w << a[i]);
  104.             zxc ^= w;
  105.             for (j = 0; j < W; j++) {
  106.                 if (zxc[j]) {
  107.                     pred[j] = a[i];
  108.                 }
  109.             }
  110.         }
  111.         for (j = 0; j < W; j++) {
  112.             if (w[j] && weight - j > 0) {
  113.                 if (min(j, weight - j) * 2 >= max(j, weight - j)) {
  114.                     vector <int> path;
  115.                     while (j > 0) {
  116.                         path.push_back(pred[j]);
  117.                         j -= pred[j];
  118.                     }
  119.                     reverse(all(path));
  120.                     cout << "YES" << endl;
  121.                     for (auto it : path) {
  122.                         cout << it << " ";
  123.                     }
  124.                     return;
  125.                 }
  126.             }
  127.         }
  128.         cout << "NO" << endl;
  129.     }
  130.     else {
  131.         cout << "NO" << endl;
  132.     }
  133. }
  134.  
  135. signed main() {
  136. #ifdef _DEBUG
  137.     freopen("input.txt", "r ", stdin);
  138.     freopen("output.txt", "w", stdout);
  139. #endif
  140.     //freopen("input.txt", "r ", stdin);
  141.     //freopen("output.txt", "w", stdout);
  142.     ios_base::sync_with_stdio(0);
  143.     cin.tie(NULL);
  144.     cout.tie(NULL);
  145.     int t = 1;
  146.     //cin >> t;
  147.     while (t--) solve();
  148. }
  149. //Deisgned by skimono
  150. //Клуб "Кольца(Серьги)"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement