제출 #712059

#제출 시각아이디문제언어결과실행 시간메모리
712059colossal_pepe은행 (IZhO14_bank)C++17
71 / 100
1075 ms7248 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...