Submission #942419

#	Time	Username	Problem	Language	Result	Execution time	Memory
942419		TrendBattles	Bank (IZhO14_bank)	C++14	100 / 100	417 ms	9036 KiB

bank

//https://oj.uz/problem/view/IZhO14_bank
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    vector <int> A(n), B(m);
    for (int& x : A) cin >> x;
    for (int& x : B) cin >> x;


    vector <vector <int>> mask_set(n);
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << m); ++mask) {
            int sum = 0;
            for (int x = mask; x; x -= x & -x) {
                sum += B[__builtin_ctz(x)];
            }

            if (sum == A[i]) mask_set[i].push_back(mask);
        }
    }

    vector <int> dp(1 << m);
    dp[0] = true;

    for (int i = 0; i < n; ++i) {
        vector <int> new_dp(1 << m);


        for (int mask = 0; mask < (1 << m); ++mask) {
            if (not dp[mask]) continue;

            for (int x : mask_set[i]) {
                if ((mask & x)) continue;

                new_dp[mask ^ x] = true;
            }
        }

        dp = move(new_dp);
    }

    cout << (*max_element(dp.begin(), dp.end()) ? "YES\n" : "NO\n");
    return 0;
}

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