제출 #1165161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165161		thinknoexit	Bank (IZhO14_bank)	C++20	100 / 100	416 ms	22056 KiB

bank

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 20;
bool dp[N + 1][1 << N];
int sum[1 << N];
int a[N + 2], b[N + 2], qs[N + 2];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        qs[i] = qs[i - 1] + a[i];
    }
    for (int i = 0;i < m;i++) cin >> b[i];
    sum[0] = 0;
    for (int bit = 0;bit < (1 << m);bit++) {
        for (int i = 0;i < m;i++) {
            if (bit & (1 << i)) continue;
            sum[bit ^ (1 << i)] = sum[bit] + b[i];
        }
    }
    dp[0][0] = 1;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            for (int bit = 0;bit < (1 << m);bit++) {
                if (!dp[i][bit]) continue;
                if (bit & (1 << j)) continue;
                if (sum[bit] + b[j] - qs[i] == a[i + 1]) {
                    dp[i + 1][bit ^ (1 << j)] = 1;
                }
                dp[i][bit ^ (1 << j)] = 1;
            }
        }
    }
    for (int i = 0;i < (1 << m);i++) {
        if (dp[n][i]) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}

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