Submission #1203371

#TimeUsernameProblemLanguageResultExecution timeMemory
1203371sopaipillaBank (IZhO14_bank)C++20
19 / 100
19 ms636 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

int n, m, ans=0;
vector<int> a, b, pf;
vector<vector<int>> subset;
void search(int i, int j) {
    int qtd=0;
    for(int k : subset[i]) qtd+=b[k];
    if(qtd==pf[i]) {
        if(i==n) {
            ans=1;
            return;
        }
        if(j==m) return;
        subset[i+1]=subset[i];
        search(i+1,0);
    } else {
        if(j==m) return;
        search(i,j+1);
        if(!(binary_search(subset[i].begin(),subset[i].end(),j))) {
            subset[i].pb(j);
            search(i,j+1);
            subset[i].pop_back();
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    a.resize(n);
    pf.resize(1,0);
    for(int &x : a) {
        cin >> x;
        pf.pb(pf.back()+x);
    }
    b.resize(m);
    for(int &x : b) cin >> x;
    
    if(n>m) {
        cout << "NO";
        return 0;
    }
    if(n==m) {
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        if(a==b) cout << "YES";
        else cout << "NO";
        return 0;
    }
    
    subset.resize(n+1);
    search(1,0);
    if(ans) cout << "YES";
    else cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...