Submission #580262

#	Time	Username	Problem	Language	Result	Execution time	Memory
580262		Neos	Bank (IZhO14_bank)	C++14	100 / 100	293 ms	16024 KiB

bank

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;

#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

const int N = 20 + 7, M = 2e4 + 7, oo = 1e9 + 7, MOD = 1e9 + 7;

int n, m, a[N], b[N];
pair<bool, int> f[1 << 20];
vector<int> num[M];

int main() {
    fastIO;
    if (fopen("test.inp", "r"))
        freopen("test.inp", "r", stdin),
        freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    for (int i = 0; i < (1 << m); i++) {
        int sum = 0;
        for (int j = 0; j < m; j++)
            if (getBit(i, j)) sum += b[j];
        num[sum].pb(i);
    }


    for (int i = 0; i < (1 << n); i++) f[i] = {0, -1};
    f[0] = {0, 0};
    for (int mask = 0; mask < (1 << n); mask++) if (!f[mask].fi)
        for (int i = 0; i < n; i++) if (getBit(mask, i) && f[mask ^ (1 << i)].se != -1) {
            int cur = ((1 << m) - 1) ^ f[mask ^ (1 << i)].se;
            for (int x: num[a[i]]) if ((cur & x) == x) {
//                if (mask == 7) cerr << f[mask ^ (1 << i)].se << endl;
                f[mask] = {1, x | f[mask ^ (1 << i)].se};
//                for (int k = 0; k < n; k++)
//                    cout << (getBit(mask, k) > 0);
//                cout << endl;
                break;
            }
        }
    cout << (f[(1 << n) - 1].fi ? "YES" : "NO");
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("test.inp", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29