Submission #1233644

#TimeUsernameProblemLanguageResultExecution timeMemory
1233644ishaanthenerdBank (IZhO14_bank)C++20
100 / 100
111 ms12768 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...