제출 #429398

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429398		SansPapyrus683	은행 (IZhO14_bank)	C++17	100 / 100	140 ms	8524 KiB

bank

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

/**
 * https://oj.uz/problem/view/IZhO14_bank
 * 2 6
 * 9 10
 * 5 4 8 6 3 11 should output NO
 */
int main() {
    int people_num;
    int note_num;
    std::cin >> people_num >> note_num;
    vector<int> people(people_num);
    vector<int> banknotes(note_num);
    for (int& p : people) {
        std::cin >> p;
    }
    for (int& b : banknotes) {
        std::cin >> b;
    }

    vector<int> leftover(1 << note_num, -1);
    vector<int> people_covered(1 << note_num, -1);
    leftover[0] = 0;
    people_covered[0] = 0;
    for (int s = 0; s < (1 << note_num); s++) {
        // cout << std::bitset<5>(s) << endl;
        for (int last = 0; last < note_num; last++) {
            if ((s & (1 << last)) == 0) {
                continue;
            }
            int prev = s & ~(1 << last);
            if (people_covered[prev] == -1) {
                continue;
            }

            int new_amt = leftover[prev] + banknotes[last];
            int 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;
            }
        }
        // cout << people_covered[s] << ' ' << leftover[s] << endl;
        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