제출 #1328841

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

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef int ll;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e6 + 5;
const ll LOG = 30;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " " << (x) << endl;

ll n, m;
ll a [30], b [30];
bool dp [30][MAXN];
vector <vll> v (30);

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }
    for(ll i = 0; i < m; i++){
        cin >> b[i];
    }
    sort(a, a+n);
    sort(b, b+m);
    ll tot = (1<<m);
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < tot; j++){
            ll cnt = 0;
            for(ll o = 0; o < m; o++){
                if((j>>o) & 1){
                    cnt += b[o];
                }
            }
            if(cnt == a[i]) v[i].push_back(j);
            // cout << i << " << ";
            // for(ll o = 0; o < m; o++){
            //     cout << ((j>>o) & 1);
            // }
            // cout << " << " << dp[i][j] << endl;
        }
    }
    for(ll i = 0; i < n; i++){
        for(auto j : v[i]){
            for(ll k = j; k < tot; k = (k+1) | j){
                if(i) dp[i][k] |= dp[i-1][k-j];
                else if(k == j) dp[i][k] = 1;
            }
        }
    }
    ll ans = 0;
    for(ll i = 0; i < tot; i++) ans |= dp[n-1][i];
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...