제출 #1189627

#제출 시각아이디문제언어결과실행 시간메모리
1189627comxdddddd은행 (IZhO14_bank)C++20
0 / 100
0 ms400 KiB
#include <bits/stdc++.h>
using namespace std;
vector<int> h(21);
vector<int> bill(21);
vector<bool> visited(21,false);
int n,m;

bool pay(int curr);

bool subset_sum(int curr, int st, int currSum) {
    if (currSum == h[curr]) {
        return pay(curr + 1);
    }
    int last = -1;
    for (int i = st; i < m; ++i) {
        if (visited[i] || bill[i] == last) continue;
        int nxt = currSum + bill[i];
        if (nxt > h[curr]) continue;
        visited[i] = true;
        if (subset_sum(curr, i + 1, nxt)) 
            return true;
        visited[i] = false;
        last = bill[i];
        if (currSum == 0) 
            break;
        if (nxt == h[curr]) 
            break;
    }
    return false;
}

bool pay(int curr) {
    if (curr == n) 
        return true;
    return subset_sum(curr, 0, 0);
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    for(int i = 0; i < m; i++){
        cin >> bill[i];
    }
    sort(h.rbegin(),h.rend());
    sort(bill.rbegin(),bill.rend());
    cout << (pay(0) ? "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...