Submission #1264613

#TimeUsernameProblemLanguageResultExecution timeMemory
1264613avohado은행 (IZhO14_bank)C++20
100 / 100
231 ms26264 KiB
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, m;
vector<int> v[20005];
int a[21], b[21], f=0;
bool ch[(int)pow(2, 20)+1][20];
void req(int mask, int j, int sum){
    if(j==m){
        return;
    }
    req(mask, j+1, sum);
    mask|=(1<<j);
    sum+=b[j];
    v[sum].pb(mask);
    req(mask, j+1, sum);
    sum-=b[j];
    mask^=(1<<j);
}
void req1(int j, int mask){
    if(j==n){
        f=1;return;
    }
    if(ch[mask][j]){
        return;
    }
    ch[mask][j]=1;
    for(auto i:v[a[j]]){
        if((mask&i)==0){
            req1(j+1, (mask|i));
        }
    }
}
void solve(){
    cin >> n >> m;
    int sum=0;
    for(int i=0; i<n; i++){
        cin >> a[i];sum+=a[i];
    }
    for(int j=0; j<m; j++){
        cin >> b[j];
    }
    req(0, 0, 0);
    req1(0, 0);
    cout << (f?"YES":"NO");
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...