제출 #942421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942421		TrendBattles	은행 (IZhO14_bank)	C++14	100 / 100	320 ms	13048 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 <int> mask_sum(1 << m);
    for (int mask = 1; mask < (1 << m); ++mask) {
        int d = __builtin_ctz(mask);

        mask_sum[mask] = mask_sum[mask ^ (1 << d)] + B[d];
    }
    vector <vector <int>> mask_set(n);
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << m); ++mask) {
            if (mask_sum[mask] == 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