제출 #1308413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308413		xnoel	은행 (IZhO14_bank)	C++20	100 / 100	313 ms	94900 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int main(){
    //freopen("1.in","r",stdin);
    int n,m;
    cin>>n>>m;
    vector<int> salary(n),notes(m);
    map<int,vector<int>> mp;
    for (int i=0;i<n;i++) {
        cin>>salary[i];
        mp[salary[i]];
    }


    for (int i=0;i<m;i++) cin>>notes[i];
    int total=(1<<m);
    vector<int> value(total,0);
    for (int mask=1;mask<total;mask++) {
        int first_bit=(1 << (31 - __builtin_clz(mask)));
        value[mask]=value[mask^first_bit]+notes[31-__builtin_clz(first_bit)];
        if (mp.find(value[mask])!=mp.end()) {
            mp[value[mask]].push_back(mask);
        }
    }

    vector<vector<int>> dp(n+1,vector<int>(total,0));
    dp[0][0]=1;
    for (int i=0;i<n;i++) {
        int num=salary[i];
        for (int mask=0;mask<total;mask++) {
            if (dp[i][mask]==0) continue;
            for (int supp_mask: mp[num]) {
                if (mask&supp_mask) continue;
                dp[i+1][mask|supp_mask]=1;
            }
        }
    }
    int ans=count(dp[n].begin(),dp[n].end(),1);
    if (ans==0) cout<<"NO\n";
    else cout<<"YES\n";

}

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