Submission #1368619

#TimeUsernameProblemLanguageResultExecution timeMemory
1368619vjudge1Bank (IZhO14_bank)C++20
100 / 100
69 ms15132 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back

const int inf=8e18;
const int N=(1LL<<21);
const int mod=998244353;
const double eps=1e-7;

int n,m;

int a[N],b[N];

vector<int>v[N];

bool memo[30][N];

bool f(int i,int p) {
    if(i==n+1) return true;
    if(memo[i][p]) return false;
    for(int mask:v[a[i]]) {
        if((mask & p)!=0)  continue;
        if(f(i+1,(p|mask))) {
            return true;
        }
    }
    memo[i][p]=1;
    return false;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    int sum=0,sum1=0;
    for(int i=1;i<=n;i++) {cin>>a[i];sum+=a[i];}
    for(int i=1;i<=m;i++) {cin>>b[i];sum1+=b[i];}
    if(sum1<sum) {
        cout<<"NO\n";
        return 0;
    }
    for(int mask=0;mask<(1<<m);mask++) {
        sum=0;
        for(int j=0;j<m;j++) {
            if((mask & (1<<j))) sum+=b[j+1];
        }
        v[sum].pb(mask);
    }
    if(f(1,0)) cout<<"YES\n";
    else cout<<"NO\n";
}
//
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...