제출 #1233614

#제출 시각아이디문제언어결과실행 시간메모리
1233614ishaanthenerd은행 (IZhO14_bank)C++20
19 / 100
88 ms12616 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a.at(i);
    for (int i = 0; i < m; i++) cin >> b.at(i);

    vector<int> sum((1 << m), 0);
    for (int mask = 1; mask < (1 << m); mask++) {
        int index = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                index = i;
                break;
            }
        }
        sum.at(mask) = sum.at(mask ^ (1 << index)) + b.at(index);
    }

    bool found = false;
    vector<int> people((1 << m), 0), leftover((1 << m), 0);
    for (int mask = 1; mask < (1 << m); mask++) {
        int most_people = 0;
        int amt_leftover = 0;
        for (int j = 0; j < m; j++) {
            if (!(mask & (1 << j))) continue;
            int cur_people = people.at(mask ^ (1 << j));
            int cur_leftover = leftover.at(mask ^ (1 << j)) + b.at(j);
            if (cur_leftover == a.at(cur_people)) {
                cur_people++;
                cur_leftover = 0;
            }
            if (cur_people > most_people) {
                most_people = cur_people;
                amt_leftover = cur_leftover;
                break;
            }
            else {
                amt_leftover = cur_leftover;
            }
        }
        people.at(mask) = most_people;
        leftover.at(mask) = amt_leftover;
        if (people.at(mask) == n) {
            found = true;
            break;
        }
    }
    cout << (found ? "YES" : "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...