제출 #1233589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233589		ishaanthenerd	은행 (IZhO14_bank)	C++20	19 / 100	85 ms	4804 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 = 1; i < n; i++) a.at(i) += a.at(i - 1);
    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));
    vector<bool> qualified((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 mask = 1; mask < (1 << m); mask++) {
        // update qualified
        for (int j = 0; j < m; j++) {
            if (!(mask & (1 << j)) && qualified.at(mask ^ (1 << j))) {
                qualified.at(mask) = true;
            }
        }
    }

    for (int i = 1; i < n; i++) {
        for (int mask = 1; mask < (1 << m); mask++) {
            if (sum.at(mask) == a.at(i) && qualified.at(mask)) {
                dp.at(i).at(mask) = true;
            }
        }
        // update qualified
        qualified = vector<bool>((1 << m), false);
        for (int mask = 1; mask < (1 << m); mask++) {
            for (int j = 0; j < m; j++) {
                if (!(mask & (1 << j)) && qualified.at(mask ^ (1 << j))) {
                    qualified.at(mask) = true;
                }
            }
        }
    }

    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: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29