Submission #1166775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166775		fonikos01	Bank (IZhO14_bank)	C++20	71 / 100	1098 ms	75480 KiB

bank

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

#define all(x) (x).begin(), (x).end()

using ll = long long;
typedef pair<ll, ll> pi;

struct node {
    node *one = nullptr;
    node *zero = nullptr;
};

int solve() {
    ll N, M; 
    cin >> N >> M;

    vector<ll> A(N);
    vector<ll> B(M);
    for(int i = 0; i < N; i++) 
        cin >> A[i];
    for(int i = 0; i < M; i++) 
        cin >> B[i];

    node *rootA = new node();
    node *curr = rootA;
    for (int i = 0; i < M; i++) {
        node *temp = new node();
        curr->zero = temp;
        curr = temp;
    }

    function<void(node*)> deleteNodes = [&](node* n) {
        if (n == nullptr) return;
        deleteNodes(n->one);
        deleteNodes(n->zero);
        delete n;
    };

    for (int i = 0; i < N; i++) {
        node *rootB = new node();
        vector<ll> dp(1 << M, -1);
        dp[0] = A[i];

        for (int mask = 0; mask < (1 << M); mask++) {
            if (dp[mask] == -1) continue;
            for (int j = 0; j < M; j++) {
                if (!(mask & (1 << j))) {
                    int newMask = mask | (1 << j);
                    dp[newMask] = max(dp[newMask], dp[mask] - B[j]);
                }
            }
        }

        for (int mask = 0; mask < (1 << M); mask++) {
            if (dp[mask] == 0) {
                node *curr = rootB;
                for (int j = 0; j < M; j++) {
                    if (mask & (1 << j)) {
                        if (curr->one == nullptr) {
                            node *temp = new node();
                            curr->one = temp;
                            curr = temp;
                        } else {
                            curr = curr->one;
                        }
                    } else {
                        if (curr->zero == nullptr) {
                            node *temp = new node();
                            curr->zero = temp;
                            curr = temp;
                        } else {
                            curr = curr->zero;
                        }
                    }
                }
            }
        }

        node *rootC = new node();
        node *currB = rootB;
        node *currC = rootC;

        vector<tuple<node*, node*, node*>> stack;
        stack.push_back({rootA, currB, currC});
        while (!stack.empty()) {
            auto [nodeA, nodeB, nodeC] = stack.back();
            stack.pop_back();

            if (nodeA->zero != nullptr && nodeB->zero != nullptr) {
                if (nodeC->zero == nullptr) {
                    nodeC->zero = new node();
                }
                stack.push_back({nodeA->zero, nodeB->zero, nodeC->zero});
            }
            if (nodeA->one != nullptr && nodeB->zero != nullptr) {
                if (nodeC->one == nullptr) {
                    nodeC->one = new node();
                } 
                stack.push_back({nodeA->one, nodeB->zero, nodeC->one});
            }
            if (nodeA->zero != nullptr && nodeB->one != nullptr) {
                if (nodeC->one == nullptr) {
                    nodeC->one = new node();
                } 
                stack.push_back({nodeA->zero, nodeB->one, nodeC->one});
            }
        }

        node* old_rootA = rootA;
        rootA = rootC;
        deleteNodes(old_rootA);
        deleteNodes(rootB);
    }

    bool can = false;
    auto dfs = [&](auto self, node *n, ll step) -> void {
        if (step == M) {
            can = true;
            return;
        }
        if (n->one != nullptr) {
            self(self, n->one, step + 1);
        }
        if (n->zero != nullptr) {
            self(self, n->zero, step + 1);
        }
    };

    dfs(dfs, rootA, 0);

    if (can) 
        cout << "YES" << '\n';
    else 
        cout << "NO" << '\n';

    deleteNodes(rootA);

    return 0;
}

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

    solve();

    return 0;
}

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