Submission #1135437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135437		eysbutno	Bank (IZhO14_bank)	C++20	100 / 100	68 ms	8520 KiB

bank

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

using ll = long long;
using pii = array<int, 2>;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto &i : a) { cin >> i; }
    for (auto &i : b) { cin >> i; }

    vector dp(1 << m, pii{-1, -1});
    dp[0] = {0, a[0]};
    for (int i = 0; i < (1 << m); i++) {
        if (dp[i][0] == -1) { continue; }
        if (dp[i][1] == 0) {
            if (dp[i][0] == n - 1) {
                cout << "YES\n";
                return 0;
            } else {
                dp[i] = {dp[i][0] + 1, a[dp[i][0] + 1]};
            }
        }

        const auto [idx, debt] = dp[i];
        // cout << i << " " << idx << " " << debt << "\n";

        for (int j = 0; j < m; j++) {
            if (i >> j & 1) { continue; }
            if (debt < b[j]) { continue; }

            dp[i | (1 << j)] = {idx, debt - b[j]};
        }
    }

    /*
    for (int i = 0; i < (1 << m); i++) {
        vector<int> stuff;
        for (int j = 0; j < m; j++) {
            if (i >> j & 1) stuff.push_back(j);
        }
        cout << "stuff ";
        for (int x : stuff) cout << x + 1 << " "; cout << "\n";
        cout << dp[i][0] << " " << dp[i][1] << "\n";
    }
    */

    cout << "NO\n";
}

/**
 * obv, we need to get everyone's money to them.
 * so basically, match subsets of stuff to ppl who need
 * 
 * cuz we need everyone done, probably have it be like,
 * dp[mask][prefix of ppl paid] = if it works
 * 
 * but transitions are cooked in that scenario
 * 
 * surely its like
 * dp[mask] = (prefix of ppl tryna pay, amount due)
 * 
 * then surely that works?
 */

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