Submission #1041211

#TimeUsernameProblemLanguageResultExecution timeMemory
1041211Antony2357111317Bank (IZhO14_bank)C++11
100 / 100
80 ms16988 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ll people_num, note_num;
  cin >> people_num >> note_num;
  vector<ll> people(people_num);
  vector<ll> banknotes(note_num);
  for(ll &p : people){ cin >> p; }
  for(ll &b : banknotes){ cin >> b; }
  vector<ll> leftover(1 << note_num, -1);
  vector<ll> people_covered(1 << note_num, -1);
  leftover[0] = 0;
  people_covered[0] = 0;
  for (ll s = 0; s < (1 << note_num); s++) {
    for (ll last = 0; last < note_num; last++) {
      if ((s & (1 << last)) == 0) { continue; }
      ll prev = s & ~(1 << last);
      if (people_covered[prev] == -1) { continue; }
      ll new_amt = leftover[prev] + banknotes[last];
      ll curr_target = people[people_covered[prev]];
      if (new_amt < curr_target) {
        people_covered[s] = people_covered[prev];
        leftover[s] = new_amt;
      }
      else if (new_amt == curr_target) {
        people_covered[s] = people_covered[prev] + 1;
        leftover[s] = 0;
      }
    }
    if (people_covered[s] == people_num) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...