제출 #1041211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041211		Antony2357111317	은행 (IZhO14_bank)	C++11	100 / 100	80 ms	16988 KiB

bank

#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;
}

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