제출 #1282556

#제출 시각아이디문제언어결과실행 시간메모리
1282556Mahog은행 (IZhO14_bank)C++20
52 / 100
1096 ms8536 KiB
#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();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...