Submission #1215419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215419		bbldrizzy	Bank (IZhO14_bank)	C++20	44 / 100	613 ms	327680 KiB

bank

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

int main() {
    int n, m; cin >> n >> m;
    vector<int> vals(n);
    vector<int> notes(m);
    for (int &u: vals) cin >> u;
    for (int &u: notes) cin >> u;
    vector<vector<int>> sum(1001, vector<int>());
    for (int i = 1; i < (1<<m); i++) {
        vector<int> nds;
        int tmp = i;
        for (int j = 0; j < m; j++) {
            if (tmp&1) nds.push_back(j);
            tmp = tmp >> 1;
        }
        int tsum = 0;
        for (int u: nds) {
            tsum += notes[u];
        }
        if (tsum <= 1000) sum[tsum].push_back(i);
        // for (int u: nds) {
        //     cout << u << " ";
        // }
        // cout << "\n";
    }
    vector<vector<int>> dp(1<<n);
    for (int i = 0; i < n; i++) {
        dp[1<<i] = sum[vals[i]];
    }
    for (int i = 1; i < (1<<n); i++) {
        vector<int> nds;
        int tmp = i;
        for (int j = 0; j < n; j++) {
            if (tmp&1) nds.push_back(j);
            tmp = tmp >> 1;
        }
        if (nds.size() == 1) continue;
        for (int j = 0; j < nds.size(); j++) {
            vector<int> maskz = dp[1<<nds[j]];
            vector<int> maskz2 = dp[i ^ (1<<nds[j])];
            for (int u: maskz) {
                for (int k: maskz2) {
                    if ((u&k) == 0) {
                        dp[i].push_back(u|k);
                    }
                }
            }
        }
    }
    if (dp[(1<<n) - 1].size() > 0) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}

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