Submission #1326562

#TimeUsernameProblemLanguageResultExecution timeMemory
1326562ayxanesedzade10Bank (IZhO14_bank)C++20
100 / 100
164 ms16808 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define ld long double
using namespace std;
int main()
{
    ll n,m;cin>>n>>m;
    ll a[n+5],b[m+5],pre[n+5];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    ll dp[(1<<m)+5],ind1[(1<<m)+5];
    pre[0]=a[0];
    for(int i=1;i<n;i++) pre[i]=pre[i-1]+a[i];
    for(int i=0;i<(1<<m)+5;i++){dp[i]=0;ind1[i]=0;}
    dp[0]=1;
    for(int mask=1;mask<(1<<m);mask++){
        ll sum=0,ind=0,s1=0;
        for(int j=0;j<m;j++){
            if(mask&(1<<j)) sum+=b[j];
        }
        for(int i=0;i<n;i++){
            if(sum>=pre[i]) ind++;
        }
        ind1[mask]=ind;
        for(int j=0;j<m;j++){
            if(mask&(1<<j)){
                ll c=mask-(1<<j);
                if(dp[c] and sum<=pre[ind1[c]]){
                    dp[mask]=1;
                }
            }
        }
        if(dp[mask] and sum==pre[n-1]){
            cout<<"YES"<<endl;return 0;
        }
    }
    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...