제출 #1098235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098235		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	20 ms	436 KiB

bank

#include <bits/stdc++.h>

using namespace std;

bool canp(int n, int m, vector<int>& a, vector<int>& b) {
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    vector<bool> used(m, false);

    function<bool(int)> backtrack = [&](int idx) {
        if (idx == n) {
            return true; 
        }

        int ca = a[idx];

        function<bool(int, int)> dfs = [&](int start, int total) {
            if (total == ca) {
                if (backtrack(idx + 1)) {
                    return true;
                }
                return false;
            }

            if (total > ca) {
                return false;
            }

            int prev = -1;
            for (int i = start; i < m; i++) {
                if (!used[i] && total + b[i] <= ca) {
                    if (b[i] == prev) {
                        continue;
                    }

                    used[i] = true; 
                    if (dfs(i + 1, total + b[i])) {
                        return true;
                    }
                    used[i] = false;
                    prev = b[i]; 
                }
            }
            return false;
        };

        return dfs(0, 0);
    };

    return backtrack(0); 
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n); 
    vector<int> b(m);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    int ta = accumulate(a.begin(), a.end(), 0);
    int tb = accumulate(b.begin(), b.end(), 0);

    if (ta > tb) {
        cout << "NO" << endl;
        return 0;
    }

    if (canp(n, m, a, b)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29