제출 #1328611

#제출 시각아이디문제언어결과실행 시간메모리
1328611somefolk은행 (IZhO14_bank)C++20
0 / 100
1096 ms12612 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;

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 = (2 << (m-1));
    vector<vector<int>> dp2(n+1, vector<int>(M, 0));

    for(int i = 1; i <= n; i++){
        int val = a[i];
        for(int mask = 0; mask < M; mask++){
            for(int bit = 0; bit < m; bit++){
                bool type = (mask & (1 << bit));
                if(type){
                    for(int j = b[bit+1]; j <= N; j++){
                        dp1[j] -= dp1[j-b[bit+1]];
                    }
                }
            }
            dp2[i][mask] += dp2[i-1][~mask] + (dp1[val] > 0);
            for(int bit = 0; bit < m; bit++){
                bool type = (mask & (1 << bit));
                if(type){
                    for(int j = N; j >= b[bit+1]; j--){
                        dp1[j] += dp1[j-b[bit+1]];
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int mask = 0; mask < M; mask++){
        // for(int bit = 0; bit < m; bit++){
        //     bool type = (mask & (1 << bit));
        //     cout << type;
        // }
        // cout << " ---> ";
        // for(int i = 1; i <= n; i++) cout << dp2[i][mask] << " ";
        // cout << endl;
        if(dp2[n][mask] == n) 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...