Submission #1204391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204391		sopaipilla	은행 (IZhO14_bank)	C++20	In queue	0 ms	0 KiB

bank

#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;
        }
        subset[i+1]=subset[i];
        search(i+1,0);
    } else if(qtd<pf[i]) {
        if(j==m) return;
        search(i,j+1);
        sort(subset[i].begin(),subset[i].end());
        if(!(binary_search(subset[i].begin(),subset[i].end(),j))) {
            subset[i].pb(j);
            search(i,j+1);
            auto it=find(subset[i].begin(),subset[i].end(),j);
            subset[i].erase(it);
        }
    }
}

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";
}