Submission #702959

#TimeUsernameProblemLanguageResultExecution timeMemory
702959ifateenBank (IZhO14_bank)C++14
100 / 100
113 ms16844 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int people_, notes_;
    cin >> people_ >> notes_;
    vector<int> people(people_);
    vector<int> notes(notes_);
    for (auto &i : people) cin >> i;
    for (auto &i : notes) cin >> i;
    vector<int> left(1 << notes_, -1) , people_covered(1 << notes_, -1);
    left[0] = 0;
    people_covered[0] = 0;
    for (int mask = 1; mask < (1 << notes_) ; mask++) {
        for (int person = 0; person < notes_; person++) {
            if ((mask & (1 << person)) == 0) {
                continue;
            }
            int prev = mask & ~(1 << person);
            if (people_covered[prev] == -1) {
                continue;
            }
            int new_amt = left[prev] + notes[person];
            int curr_target = people[people_covered[prev]];
            if (new_amt < curr_target) {
                people_covered[mask] = people_covered[prev];
                left[mask] = new_amt;
            }
            else if (new_amt == curr_target) {
                people_covered[mask] = people_covered[prev] + 1;
                left[mask] = 0;
            }
        }
        if (people_covered[mask] == people_) {
            cout << "YES\n";
            goto end;
        }
    }
    cout << "NO\n";
    end:;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...