Submission #1325808

#TimeUsernameProblemLanguageResultExecution timeMemory
1325808madiBank (IZhO14_bank)C++20
100 / 100
145 ms8636 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define ld long double
#define all(x) x.begin(),x.end()
using namespace std;

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

ll dp[(1ll<<21)];

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

int main(){
    //freopen("mail.in","r",stdin);
    //freopen("mail.out","w",stdout);
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int test=1;
    //cin>>test;
    for(int i=1ll;i<=test;i++){
        solve();
    }
    return 0ll;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...