제출 #1312069

#제출 시각아이디문제언어결과실행 시간메모리
1312069tschav_은행 (IZhO14_bank)C++20
100 / 100
374 ms28908 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    vector<int> dp[1001];
    for (int i = 0; i < (1 << m); ++i) {
        int sum = 0;
        for (int j = 0; j < m; ++j) {
            if (i & (1 << j)) {
                sum += b[j];
            }
        }
        if (sum <= 1000) {
            dp[sum].push_back(i);
        }
    }
    int prev[(1 << m)];
    int cur[(1 << m)];
    for (int j = 0; j < (1 << m); ++j) {
        prev[j] = cur[j] = false;
    }
    for (int i: dp[a[0]]) {
        prev[i]++;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < (1 << m); ++j) {
            if (!prev[j]) {
                continue;
            }
            for (int val: dp[a[i]]) {
                if ((val & j) == 0) {
                    cur[val + j] += prev[j];
                }
            }
        }
        for (int j = 0; j < (1 << m); ++j) {
            prev[j] = cur[j];
            cur[j] = false;
        }
    }
    bool bo = false;
    for (int i = 0; i < (1 << m); ++i) {
        bo = bo or prev[i];
    }
    if (bo) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...