제출 #1282556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282556		Mahog	은행 (IZhO14_bank)	C++20	52 / 100	1096 ms	8536 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 22;
int a[MAX], b[MAX], f[MAX][1 << 20], g[1 << 20], n, m;

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            if ((i >> j) % 2 == 1) g[i] += b[j + 1];
        }
    }
    for (int i = 0; i < (1 << m); i++) f[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << m); j++) {
            for (int k = j; k > 0; k = (k - 1) & j) {
                if (g[k] == a[i]) f[i][j] = max(f[i][j], f[i - 1][j - k]);
            }
        }
    }
    cout << (f[n][(1 << m) - 1] ? "YES" : "NO");
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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