Submission #685414

#	Time	Username	Problem	Language	Result	Execution time	Memory
685414		zeroesandones	Bank (IZhO14_bank)	C++17	100 / 100	116 ms	16744 KiB

bank

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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb push_back

void solve()
{
    ll n, m;
    cin >> n >> m;

    ll a[n];
    FOR(i, 0, n)
        cin >> a[i];
    ll b[m];
    FOR(i, 0, m)
        cin >> b[i];

    ll paid[(1<<m)]; // no. of people in the prefix of a paid wih subset s
    ll left[(1<<m)]; // amount of money left if people in subset s were paid
                     
    memset(paid, -1, sizeof(paid));
    memset(left, -1, sizeof(left));

    paid[0] = 0;
    left[0] = 0;

    FOR(i, 1, (1<<m)) {
        FOR(j, 0, m) {
            if(!(i & (1<<j)))
                continue;
            ll prev = i ^ (1<<j);

            if(paid[prev] == -1) continue;

            ll val = left[prev] + b[j];
            ll tar = a[paid[prev]];

            if(val < tar) {
                paid[i] = paid[prev];
                left[i] = val;
            } else if(val == tar) {
                paid[i] = paid[prev] + 1;
                left[i] = 0;
            }
        }

        if(paid[i] == n) {
            cout << "YES" << nl;
            return;
        }
    }

    cout << "NO" << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

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