제출 #702959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702959		ifateen	은행 (IZhO14_bank)	C++14	100 / 100	113 ms	16844 KiB

bank

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

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