Submission #1263739

#TimeUsernameProblemLanguageResultExecution timeMemory
1263739backBank (IZhO14_bank)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> a, b;
vector<int> used;
bool ok = false;

void dfs(int idx, int sum) {
    if (ok) return; // đã tìm được thì cắt
    if (sum == a[idx]) {
        if (idx == n - 1) { ok = true; return; }
        dfs(idx + 1, 0); // sang người tiếp theo
        return;
    }
    for (int j = 0; j < m; j++) {
        if (!used[j] && sum + b[j] <= a[idx]) {
            used[j] = 1;
            dfs(idx, sum + b[j]);
            used[j] = 0;
            if (ok) return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int j = 0; j < m; j++) cin >> b[j];
    if (accumulate(a.begin(), a.end(), 0LL) != accumulate(b.begin(), b.end(), 0LL)) {
        cout << "NO\n"; return 0;
    }
    sort(a.rbegin(), a.rend()); // người nhiều tiền trước
    sort(b.rbegin(), b.rend()); // tiền to trước
    used.assign(m, 0);
    dfs(0, 0);
    cout << (ok ? "YES\n" : "NO\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...