Submission #757269

#	Time	Username	Problem	Language	Result	Execution time	Memory
757269		thimote75	Bank (IZhO14_bank)	C++14	100 / 100	954 ms	16548 KiB

bank

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

const int MAX_N = 20;
const int MAX_M = 20;
const int MAX_MASK = 1 << MAX_M;

int dp[MAX_MASK];

idata salary;
igrid transitions;

int main () {
    int N, M; cin >> N >> M;

    salary.resize(N);
    transitions.resize(N);

    for (int iN = 0; iN < N; iN ++) {
        int x;
        cin >> x;

        salary[iN] = x;
    }

    for (int iM = 0; iM < M; iM ++) {
        int x;
        cin >> x;

        for (int mask = 0; mask < (1 << iM); mask ++)
            dp[mask + (1 << iM)] = dp[mask] + x;
    }

    for (int mask = 0; mask < (1 << M); mask ++) {
        for (int i = 0; i < N; i ++) {
            if (dp[mask] != salary[i]) continue ;

            transitions[i].push_back(mask);
        }
    }

    unordered_set<int> mask_array; mask_array.insert(0);
    for (int i = 0; i < N; i ++) {
        unordered_set<int> next_mask_array;

        for (int mask : mask_array) {
            for (int next : transitions[i]) {
                if (next & mask) continue ;

                next_mask_array.insert(next | mask);
            }
        }

        mask_array = next_mask_array;
    }

    if (mask_array.size() != 0) cout << "YES\n";
    else cout << "NO\n";
}

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