Submission #1089263

#TimeUsernameProblemLanguageResultExecution timeMemory
1089263vjudge1Bank (IZhO14_bank)C++17
100 / 100
17 ms456 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<int>a;
vector<int>b;
vector<bool>used;
bool rec(int j) {
    if (j==n)return 1;
    int cur=a[j];
    if(cur==0)return rec(j+1);
    function<bool(int, long long, long long)> dfs = [&](int start, long long t, long long p) -> bool {
        if (t==cur) {
            return rec(j+1);
        }
        if (t>cur) {
            return 0;
        }
        for (int i=start; i<m; ++i) {
            if (!used[i] && t+b[i]<=cur) {
                if (i>start && b[i]==b[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i]=1;
                if (dfs(i + 1, t+b[i], b[i])){
                    return 1;
                }
                used[i]=0;
            }
        }
        return 0;
    };

    return dfs(0, 0, -1);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    a.resize(n);
    b.resize(m);
    used.resize(m, false);
    int tot=0, bank=0;
    for(int i=0; i<n; ++i){
        cin>>a[i];
        tot+=a[i];
    }
    for(int i=0; i<m; ++i){
        cin>>b[i];
        bank+=b[i];
    }
    sort(a.begin(), a.end(), greater<long long>());
    sort(b.begin(), b.end(), greater<long long>());
    if(tot>bank){
        cout<<"NO";
        return 0;
    }
    if(!rec(0)) cout << "NO";
    else cout << "YES";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...