제출 #1306710

#제출 시각아이디문제언어결과실행 시간메모리
1306710hectormedranoBank (IZhO14_bank)C++20
71 / 100
1095 ms17112 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, M;
vector<ll> a, b;
vector<pair<ll, ll>> s;
vector<vector<ll>> c;

bool calc(ll w, ll x){
    if(x==0){return true;}
    if(w==0){return false;}
    bool r = false;
    ll w_ = (1<<M) - 1 - w;
    for(ll val : c[x-1]){
        //cout<<"Para "<<w<<" y "<<x<<": "<<w_<<" "<<val<<endl;
        if((w_ xor val) != (w_ + val)){continue;}
        r = (r or calc(w-val, x-1));
    }
    return r;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin>>N>>M;
    a.resize(N);
    b.resize(M);
    s.resize(1<<M);
    c.resize(N);
    for(ll i=0;i<N;i++){cin>>a[i];}
    for(ll i=0;i<M;i++){cin>>b[i];}
    sort(a.begin(), a.end());
    s[0] = {0, 0};
    for(ll i=1;i<=M;i++){
        for(ll j=(1<<(i-1));j<(1<<i);j++){
            s[j].first = s[j-(1<<(i-1))].first + b[i-1];
            s[j].second = j;
            //cout<<s[j].first<<endl;
        }
    }
    //for(pair<ll, ll> val : s){cout<<val.first<<endl;}
    sort(s.begin(), s.end());
    for(ll i=0;i<N;i++){
        pair<ll, ll> p1 = {a[i], 1<<M};
        pair<ll, ll> p2 = {a[i], -1};
        auto it1 = upper_bound(s.begin(), s.end(), p1);
        auto it2 = lower_bound(s.begin(), s.end(), p2);
        if(it2 == s.end()){continue;}
        ll x, y;
        if(it1 == s.end()){x = 1<<M;}
        else{x = it1 - s.begin();}
        y = it2 - s.begin();
        for(ll j=y;j<x;j++){
            c[i].push_back(s[j].second);
        }
    }
    if(calc((1<<M) - 1, N)){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...