Submission #980438

#	Time	Username	Problem	Language	Result	Execution time	Memory
980438		54skyxenon	Bank (IZhO14_bank)	C++17	100 / 100	111 ms	8792 KiB

bank

// https://oj.uz/problem/view/IZhO14_bank 

#include <bits/stdc++.h>
using namespace std;

pair<int, int> better(pair<int, int> p1, pair<int, int> p2) {
    if (p1.first != p2.first) {
        return p1.first > p2.first ? p1 : p2;
    }
    return p1.second >= p2.second ? p1 : p2;
}

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

    int n, m;
    cin >> n >> m;

    vector<int> A(n);
    for (int& a : A) {
        cin >> a;
    }

    vector<int> B(m);
    for (int& b : B) {
        cin >> b;
    }

    vector<pair<int, int>> dp(1 << m);

    for (int bitmask = 1; bitmask < (1 << m); bitmask++) {
        for (int last = 0; last < m; last++) {
            if (!(bitmask & (1 << last))) {
                continue;
            }

            int previous = bitmask ^ (1 << last);
            auto [employee, remaining] = dp[previous];
            int sum = remaining + B[last];

            // Matches the current employee's salary, can go to the next one
            pair<int, int> state;
            if (sum == A[employee]) {
                state = {employee + 1, 0};
            }
            // Push this banknote onto the leftover amount
            else {
                state = {employee, sum};
            }

            dp[bitmask] = better(dp[bitmask], state);
        }

        if (dp[bitmask].first == n) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";
}

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