Submission #1098184

#TimeUsernameProblemLanguageResultExecution timeMemory
1098184vjudge1Bank (IZhO14_bank)C++17
19 / 100
1 ms604 KiB
#include <iostream>
#include <vector>
#include <algorithm>

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()); 

    for (int i = 0; i < n; i++) {
        int ca = a[i];
        vector<bool> dp(ca + 1, false); 
        dp[0] = true;

        for (int ba = 0; ba < m; ba++) {
            for (int j = ca; j >= b[ba]; j--) {
                if (dp[j - b[ba]]) {
                    dp[j] = true;
                }
            }
        }

        auto it = upper_bound(b.begin(), b.end(), ca);
        if (it != b.begin() && *(--it) == ca) {
            b.erase(it); 
            continue; 
        }

        if (!dp[ca]) {
            return false;
        }

        int ra = ca;
        for (int ba = m - 1; ba >= 0 && ra > 0; ba--) {
            if (ra >= b[ba] && dp[ra - b[ba]]) {
                ra -= b[ba];
                b[ba] = -1; 
            }
        }

        b.erase(remove(b.begin(), b.end(), -1), b.end());
        m = b.size(); 
    }

    return true; 
}

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

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

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...