Submission #1328882

#TimeUsernameProblemLanguageResultExecution timeMemory
1328882somefolk은행 (IZhO14_bank)C++20
52 / 100
1096 ms12612 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1), b(m+1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];

    if(n > m){
        cout << "NO" << endl;
        return;
    }

    vector<int> dp1(N+1, 0); dp1[0] = 1;
    for(int i = 1; i <= m; i++){
        for(int j = N; j >= b[i]; j--){
            dp1[j] += dp1[j-b[i]];
        }
    }

    int M = (1 << m);
    vector<vector<int>> dp2(n+1, vector<int>(M, 0));
    dp2[0][0] = 1;

    for(int i = 1; i <= n; i++){
        int need = a[i];
        for(int mask = 0; mask < M; mask++){
            if(!dp2[i-1][mask]) continue;
            int free = (~mask) & (M-1);
            for(int sub = free; sub; sub = (sub-1) & free){
                vector<int> dpcpy = dp1;
                int used = mask | sub;
                for(int bit = 0; bit < m; bit++){
                    if(used & (1<<bit)){
                        int w = b[bit+1];
                        for(int s = w; s <= N; s++){
                            dpcpy[s] -= dpcpy[s-w];
                        }
                    }
                }
                int sum = 0;
                for(int bit = 0; bit < m; bit++){
                    if(sub & (1<<bit)) sum += b[bit+1];
                }
                if(sum == need) dp2[i][mask | sub] = 1;
            }
        }
    }

    int ans = 0;
    for(int mask = 0; mask < M; mask++){
        if(dp2[n][mask]) ans = 1;
    }

    cout << (ans ? "YES" : "NO") << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...