제출 #1312069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312069		tschav_	은행 (IZhO14_bank)	C++20	100 / 100	374 ms	28908 KiB

bank

#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";
    }
}

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