Submission #1323532

#TimeUsernameProblemLanguageResultExecution timeMemory
1323532adiddyBank (IZhO14_bank)C++20
100 / 100
153 ms8504 KiB
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define pb push_back
#define ent "\n"
#define F first
#define S second
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
using namespace std;

const ll inf=1e18;
const ll mod=1e9+7;
const ll maxn=2e5+5;

ll binpow(ll a,ll n){
    if(n==0) return 1;
    if(n==1) return a;
    if(n%2==1) return binpow(a,n-1)*a%mod;
    ll x=binpow(a,n/2);
    return x*x%mod;
}



void solve(){
    ll n,m;
    cin>>n>>m;
    ll a[n+5],b[m+5];
    vector < ll > dp((1ll<<m),0);
    for(ll i=0;i<n;i++){
        cin>>a[i];
        if(i>0) a[i]+=a[i-1];
    }
    for(ll i=0;i<m;i++) cin>>b[i];
    for(ll mask=0;mask<(1ll<<m);mask++){
        if(dp[mask]==n) continue;
        ll pos=dp[mask];
        ll x=a[pos];
        for(ll j=0;j<m;j++){
            if((mask&(1ll<<j))) x-=b[j];
        }
        for(ll j=0;j<m;j++){
            if((mask&(1ll<<j))) continue;
            if(x>=b[j]) dp[(mask|(1ll<<j))]=max(dp[(mask|(1ll<<j))],dp[mask]+(x==b[j]));
        }
    }
    for(ll mask=0;mask<(1ll<<m);mask++){
        if(dp[mask]==n){
            cout<<"YES";
            return;
        }
    }
    cout<<"NO";
}

/*
*/

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