제출 #464706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464706		asdf1234coding	은행 (IZhO14_bank)	C++14	100 / 100	131 ms	8644 KiB

bank

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

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