제출 #854304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854304		WebbWayne	은행 (IZhO14_bank)	C++14	100 / 100	99 ms	8640 KiB

bank

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i, a, b) for(int i = a; i < b; i++)
#define vi vector<int> 
#define ii pair<int, int>
#define pb push_back
#define f first
#define s second
#define all(i) (i).begin(), (i).end()
#define MOD 1000000007
#define endl '\n'

int main() {
    int n, m;
    cin>>n>>m;

    vi salary(n);
    vi bank(m);

    rep(i, 0, n) 
        cin>>salary[i];
    rep(j, 0, m) 
        cin>>bank[j];

    vi covered(1<<m, -1);
    vi leftover(1<<m, -1);

    covered[0] = 0;
    leftover[0] = 0;

    for(int mask = 0; mask < (1<<m); mask++) {
        for(int take = 0; take < m; take++) {
            if((mask & (1<<take)) == 0) continue;
            int prev = mask & ~(1<<take);
            if(covered[prev] == -1) continue;

            int cur = leftover[prev] + bank[take];
            int req = salary[covered[prev]];
 
            if(cur < req) {
                covered[mask] = covered[prev];
                leftover[mask] = cur;
            }

            else if(cur == req) {
                leftover[mask] = 0;
                covered[mask] = covered[prev] + 1;
            } 
        }

        if(covered[mask] == 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