Submission #1233644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233644		ishaanthenerd	Bank (IZhO14_bank)	C++20	100 / 100	111 ms	12768 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a.at(i);
    for (int i = 0; i < m; i++) cin >> b.at(i);

    vector<int> sum((1 << m), 0);
    for (int mask = 1; mask < (1 << m); mask++) {
        int index = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                index = i;
                break;
            }
        }
        sum.at(mask) = sum.at(mask ^ (1 << index)) + b.at(index);
    }

    vector<int> people((1 << m), -1), leftover((1 << m), -1);
    people.at(0) = 0;
    leftover.at(0) = 0;
    for (int mask = 1; mask < (1 << m); mask++) {
        for (int j = 0; j < m; j++) {
            if (!(mask & (1 << j))) continue;
            if (people.at(mask ^ (1 << j)) == -1) continue;

            int ppl = people.at(mask ^ (1 << j));
            int lft = leftover.at(mask ^ (1 << j)) + b.at(j);
            if (lft < a.at(ppl)) {
                people.at(mask) = ppl;
                leftover.at(mask) = lft;
            }
            else if (lft == a.at(ppl)) {
                people.at(mask) = ppl + 1;
                leftover.at(mask) = 0;
            }
        }

        if (people.at(mask) == n) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;

    return 0;
}

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