제출 #1115809

#제출 시각아이디문제언어결과실행 시간메모리
1115809nanghongg은행 (IZhO14_bank)C++14
71 / 100
1062 ms21072 KiB
#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define ll long long
#define ld long double

#define PI 3.1415926535897932384626433832795l;

int a[21]; int b[21];
bool dp[21][1<<21];

void solve(){
    int n,m; cin >> n >> m;
    map<int,int>mp;
    for (int i=1; i<=n; i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    vector<vector<int>>can(1001);
    for (int i=0; i<m; i++) cin >> b[i];
    for (int mask=0; mask<(1<<m); mask++){
        int sum=0;
        for (int i=0; i<m; i++){
            if (mask&(1<<i)){
                sum+=b[i];
            }
        }
        if (n==1 && sum==a[1]){
            cout << "YES";
            return;
        }
        if (mp[sum]) can[sum].push_back(mask);
    }
    if (n==1) {cout << "NO"; return;}
    dp[0][0]=true;
    for (int i=1;i<=n; i++){
        for (int mask=0; mask<(1<<m); mask++){
            for (auto can_mask:can[a[i]]){
                if ((can_mask&mask)!=can_mask) continue;
                int pre_mask=(can_mask^mask);
                if (dp[i-1][pre_mask]) {
                    dp[i][mask] = true;
                    if(i==n){
                        cout << "YES";
                        return;
                    }
                    break;
                }
            }
        }
    }
    cout << "NO";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...