Submission #1350542

#TimeUsernameProblemLanguageResultExecution timeMemory
1350542khba은행 (IZhO14_bank)C++20
100 / 100
491 ms7160 KiB
// author: khba

#include "bits/stdc++.h"

using namespace std;
#ifdef khba
#include "C:\Users\Asus\Desktop\khba\debug.h"
#else
#define print(...) 42
#endif

const int N = 1 << 20;

int32_t main() {
#ifdef khba
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    // freopen("promote.in", "r", stdin);
    // freopen("promote.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    vector<vector<int>> pos(1001);
    for (int& i : a) cin >> i;
    for (int& i : b) cin >> i;
    for (int mask = 0; mask < (1 << m); ++mask) {
        int sum = 0;
        for (int i = 0; i < m; ++i) sum += (mask >> i & 1) * b[i];
        if (sum <= 1000) pos[sum].push_back(mask);
    }
    bitset<N> dp = 0;
    dp[0] = true;
    for (int i = 0; i < n; ++i) {
        bitset<N> ndp = 0;
        for (int& j : pos[a[i]]) {
            int l = ((1 << m) - 1) ^ j;
            for (int msk = l;; msk = (msk - 1) & l) {
                if (dp[msk]) ndp[msk | j] = true;
                if (msk == 0) break;
            }
        }
        dp = ndp;
    }
    cout << (dp.any() ? "YES" : "NO");
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...