Submission #1339783

#TimeUsernameProblemLanguageResultExecution timeMemory
1339783nathlol2은행 (IZhO14_bank)C++20
71 / 100
134 ms10292 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m, ans, a[N], b[N];
bool dp[N][(1 << N)];
vector<int> c[20005];

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

    cin >> n >> m;
    for(int i = 0;i<n;i++) cin >> a[i];
    for(int i = 0;i<m;i++) cin >> b[i];
    for(int msk = 0;msk<(1 << m);msk++){
        int sm = 0;
        for(int i = 0;i<m;i++){
            if(msk & (1 << i)) sm += b[i];
        }
        c[sm].push_back(msk);
    }
    dp[0][0] = 1;
    for(int i = 0;i<n;i++){
        for(int msk = 0;msk<(1 << m);msk++){
            if(dp[i][msk]){
                for(auto x : c[a[i]]) if(!(x & msk)) dp[i + 1][x | msk] = 1;
            }
        }
    }
    for(int msk = 0;msk<(1 << m);msk++) ans |= dp[n][msk];
    if(ans) cout << "YES";
    else cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...