제출 #1013050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013050		aufan	Bank (IZhO14_bank)	C++17	71 / 100	1058 ms	211604 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        vector<int> b(m);
        for (int i = 0; i < m; i++) cin >> b[i];

        vector<int> sum(1 << m);
        for (int i = 0; i < (1 << m); i++) {
                for (int j = 0; j < m; j++) {
                        if (i >> j & 1) {
                                sum[i] += b[j];
                        }
                }
        }

        vector<int> dp;
        dp.push_back(0);
        for (int i = 0; i < n; i++) {
                vector<int> ndp;
                for (int j = 0; j < (1 << m); j++) {
                        if (sum[j] == a[i]) {
                                for (auto mask : dp) {
                                        if ((j & mask) == 0) {
                                                ndp.push_back(j | mask);
                                        }
                                }
                        }
                }
                sort(ndp.begin(), ndp.end());
                ndp.erase(unique(ndp.begin(), ndp.end()), ndp.end());
                
                swap(dp, ndp);
        }

        cout << (!dp.empty() ? "YES" : "NO") << '\n';
        
        return 0;
}

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