제출 #1233579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233579		ishaanthenerd	은행 (IZhO14_bank)	C++20	71 / 100	1094 ms	4936 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a.at(i);
    for (int i = 0; i < m; i++) cin >> b.at(i);

    vector<int> sum((1 << m), 0);
    for (int mask = 1; mask < (1 << m); mask++) {
        int index = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                index = i;
                break;
            }
        }
        sum.at(mask) = sum.at(mask ^ (1 << index)) + b.at(index);
    }

    vector<vector<bool>> dp(n, vector<bool>((1 << m), false));
    for (int mask = 1; mask < (1 << m); mask++) {
        if (sum.at(mask) == a.at(0)) {
            dp.at(0).at(mask) = true;
        }
    }
    for (int i = 1; i < n; i++) {
        for (int mask = 1; mask < (1 << m); mask++) {
            for (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
                int subset = mask ^ submask;
                if (dp.at(i - 1).at(subset) && sum.at(submask) == a.at(i)) {
                    dp.at(i).at(mask) = true;
                    break;
                }
            }
        }
    }

    bool works = false;
    for (int mask = 1; mask < (1 << m); mask++) {
        if (dp.back().at(mask)) {
            works = true;
            break;
        }
    }
    cout << (works ? "YES" : "NO") << endl;

    return 0;
}

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