제출 #1279284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279284		haithamcoder	은행 (IZhO14_bank)	C++20	0 / 100	1095 ms	12916 KiB

bank

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll A = 1000;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);


int main() {
    Algerian OI

    ll n, m;

    cin >> n >> m;
    vector<ll> a(n), b(m);

    for (ll i = 0; i < n; i++) cin >> a[i];
    for (ll i = 0; i < m; i++) cin >> b[i];

    vector<vector<ll>> sum(A + 1);

    for (ll i = 0; i < (1 << m); i++) {
        ll s = 0;

        for (ll j = 0; j < m; j++) {
            if ((i >> j) & 1) s += b[j];
        }

        if (s <= A) sum[s].push_back(i);
    }

    vector<vector<bool>> dp(n + 1, vector<bool>(1 << m, 0));

    for (ll i = 0; i < (1 << m); i++) dp[n][i] = 1;

    for (ll i = n - 1; i >= 0; i--) {
        for (ll mask = 0; mask < (1 << m); mask++) {
            for (auto subset : sum[a[i]]) {
                if (mask & subset == subset) {
                    if (dp[i + 1][mask ^ subset] == 1) { dp[i][mask] = 1; break; }
                }
            }
        }
    }

    cout << (dp[0][(1 << m) - 1] ? "YES\n" : "NO\n");

    return 0;
}

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