제출 #712059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712059		colossal_pepe	은행 (IZhO14_bank)	C++17	71 / 100	1075 ms	7248 KiB

bank

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int n, m;
vector<int> a, b, s;

int main() {
    { // input
        cin >> n >> m;
        a.resize(n), b.resize(m);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < m; i++) {
            cin >> b[i];
        }
    }
    { // mask sum
        s.resize(1 << m, 0);
        for (int c = 0; c < (1 << m); c++) {
            for (int i = 0; i < m; i++) {
                if (c&(1 << i)) s[c] += b[i];
            }
            // cout << c << ' ' << s[c] << endl;
        }
    }
    { // main
        sort(a.begin(), a.end());
        vector<int> valid;
        for (int c = 0; c < (1 << m); c++) {
            if (s[c] == a[0]) valid.push_back(c);
        }
        for (int i = 1; i < n; i++) {
            vector<int> new_valid;
            for (int c = 0; c < (1 << m); c++) {
                if (s[c] != a[i]) continue;
                for (int c_prv : valid) {
                    if ((c_prv | c) == c_prv + c) new_valid.push_back(c_prv + c);
                }
            }
            valid = new_valid;
        }
        cout << (valid.empty() ? "NO" : "YES") << '\n';
    }
    return 0;
}

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