제출 #965501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965501		0x34c	은행 (IZhO14_bank)	C++17	100 / 100	117 ms	16980 KiB

bank

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> ppl(N + 1), mny(M);
    for(int i = 0; i < N; i++)
        cin >> ppl[i];
    ppl[N] = numeric_limits<int>::max();
    
    for(int j = 0; j < M; j++)
        cin >> mny[j];

    vector<int> pref_sol(1 << M, -1);
    vector<int> cur_sol(1 << M, 0);
    pref_sol[0] = 0;

    for(int mask = 1; mask < (1 << M); mask++) {
        for(int pick = 0; pick < M; pick++) {
            if((mask & (1 << pick)) == 0)
                continue;
            
            int prev = mask & (~(1 << pick));
            if(pref_sol[prev] == -1)
                continue;

            if(cur_sol[prev] + mny[pick] > ppl[pref_sol[prev]])
                continue;
            else if(cur_sol[prev] + mny[pick] < ppl[pref_sol[prev]]) {
                cur_sol[mask] = cur_sol[prev] + mny[pick];
                pref_sol[mask] = pref_sol[prev];
            }
            else {
                cur_sol[prev] += mny[pick];
                pref_sol[mask] = 1 + pref_sol[prev];
            }
        }
    }

    if(pref_sol[(1 << M) - 1] == N) {
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;
}

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