Submission #464706

#TimeUsernameProblemLanguageResultExecution timeMemory
464706asdf1234codingBank (IZhO14_bank)C++14
100 / 100
131 ms8644 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define MOD (ll) (1e9+7)

int main() {
    ios_base::sync_with_stdio(false);
    int n,m; cin>>n>>m;
    vector<int> people(n);
    for(int i=0; i<n; i++) cin>>people[i];
    vector<int> banknotes(m);
    for(int i=0; i<m; i++) cin>>banknotes[i];

    vector<int> people_paid(1<<m,-1);
    vector<int> leftover(1<<m, -1);

    leftover[0]=0;
    people_paid[0]=0;
    
    for(int subset = 1; subset<(1<<m); subset++) {
        for(int last = 0; last<m; last++) {
            if(!(subset&(1<<last))) continue;
            int prev = subset-(1<<last);
            if(people_paid[prev]==-1) continue;
            int money_left = leftover[prev] + banknotes[last];
            int next_target = people[people_paid[prev]];
            if(money_left<next_target) {
                people_paid[subset] = people_paid[prev];
                leftover[subset] = money_left;
            } else if (money_left == next_target) {
                people_paid[subset] = people_paid[prev] + 1;
                leftover[subset] = 0;
            } else {
                // nothing, we dont wanna update anything and try to make amount of money for next person with other values
            }
        }
        if(people_paid[subset] == 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...