제출 #1205001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205001		sopaipilla	은행 (IZhO14_bank)	C++20	100 / 100	236 ms	127764 KiB

bank

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

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    int tot=0;
    for(int &x : a) {
        cin >> x;
        tot+=x;
    }
    sort(a.begin(),a.end());
    vector<int> b(m);
    for(int &x : b) cin >> x;
    sort(b.begin(),b.end());
    
    if(n>m) {
        cout << "NO";
        return 0;
    }
    if(n==m) {
        if(a==b) cout << "YES";
        else cout << "NO";
        return 0;
    }
    
    vector<vector<int>> get(tot+1);
    get[0]={0};
    for(int i=0; i<m; ++i) {
        for(int e=tot; e>=b[i]; --e) {
            for(int from : get[e-b[i]]) {
                if((from & (1<<i))) continue;
                get[e].pb((from|(1<<i)));
            }
        }
    }

    vector<vector<int>> dp((1<<m),vector<int>(n,0));
    for(int mask : get[a[0]]) dp[mask][0]=1;
    for(int i=0; i<(n-1); ++i) {
        for(int mask=1; mask<(1<<m); ++mask) {
            if(!dp[mask][i]) continue;
            for(int proxmask : get[a[i+1]]) {
                if((mask & proxmask)) continue;
                dp[(mask|proxmask)][i+1]=1;
            }
        }
    }

    for(int mask=1; mask<(1<<m); ++mask) {
        if(dp[mask][n-1]) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
}

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