Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize("no-stack-protector")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- //#pragma GCC optimize("fast-math")
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <list>
- #include <unordered_map>
- #include <unordered_set>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef short sh;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef string str;
- //typedef __int128 ultraint;
- #define sqrt sqrtl
- #define F first
- #define S second
- #define endl '\n'
- #define all(vc666) vc666.begin(), vc666.end()
- #define allr(vc666) vc666.rbegin(), vc666.rend()
- //#define int long long
- #define degug(x) cerr (#x) << " " << (x) << endl;
- const ll INF = 3e18 + 3;
- const ll inf = 1e9 + 3;
- const ll ONE = 1, ZERO = 0;
- const ll mod = 1e9 + 7;
- const ll m1 = 1e9 + 575179;
- const ll m2 = 1e9 + 87;
- const ll LG = 31;
- const ll k = 347;
- //const ll k_sqrt = 400;
- //const ll p = 106033;
- ld EPS = 1e-9;
- ld PI = 3.1415926535897932384;
- ld phi = (sqrt(5) + 1.0) / 2.0;
- mt19937_64 gen(40906);
- const int N = 1e3 + 10;
- const int W = 1e2;
- int a[N];
- bitset <W> w;
- bitset <W> zxc;
- int pred[W];
- void solve() {
- int n, i, j, weight = 0;
- cin >> n;
- for (i = 0; i < n; i++) {
- cin >> a[i];
- weight += a[i];
- }
- if (n <= 20) {
- int N = (1 << n);
- int s1 = 0, s2 = 0, mask;
- for (mask = 0; mask < N; mask++) {
- s1 = 0, s2 = 0;
- for (i = 0; i < n; i++) {
- if (mask & (ONE << i)) {
- s1 += a[i];
- }
- else {
- s2 += a[i];
- }
- }
- if (min(s1, s2) * (int)2 >= max(s1, s2)) {
- cout << "YES" << endl;
- for (i = 0; i < n; i++) {
- if (mask & (ONE << i)) {
- cout << a[i] << " ";
- }
- }
- return;
- }
- }
- cout << "NO" << endl;
- }
- else if (weight / 3 < W) {
- w[0] = 1;
- for (i = 0; i < n; i++) {
- w |= (w << a[i]);
- zxc ^= w;
- for (j = 0; j < W; j++) {
- if (zxc[j]) {
- pred[j] = a[i];
- }
- }
- }
- for (j = 0; j < W; j++) {
- if (w[j] && weight - j > 0) {
- if (min(j, weight - j) * 2 >= max(j, weight - j)) {
- vector <int> path;
- while (j > 0) {
- path.push_back(pred[j]);
- j -= pred[j];
- }
- reverse(all(path));
- cout << "YES" << endl;
- for (auto it : path) {
- cout << it << " ";
- }
- return;
- }
- }
- }
- cout << "NO" << endl;
- }
- else {
- cout << "NO" << endl;
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r ", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- //freopen("input.txt", "r ", stdin);
- //freopen("output.txt", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- int t = 1;
- //cin >> t;
- while (t--) solve();
- }
- //Deisgned by skimono
- //Клуб "Кольца(Серьги)"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement