Submission #1204403

#TimeUsernameProblemLanguageResultExecution timeMemory
1204403sopaipillaBank (IZhO14_bank)C++20
71 / 100
1093 ms436 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fst first
#define snd second
using namespace std;

int n, m, ans=0;
vector<int> a, b, pf;
vector<pair<int,set<int>>> subset;
void search(int i, int j) {
    int qtd=subset[i].fst;
    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);
        if(subset[i].snd.find(j)==subset[i].snd.end()) {
            subset[i].snd.insert(j);
            subset[i].fst+=b[j];
            search(i,j+1);
            subset[i].snd.erase(j);
            subset[i].fst-=b[j];
        }
    }
}

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...