제출 #1115803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115803		nanghongg	은행 (IZhO14_bank)	C++14	71 / 100	1062 ms	21328 KiB

bank

#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;

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

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

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