제출 #887480

#제출 시각아이디문제언어결과실행 시간메모리
887480Perl32은행 (IZhO14_bank)C++14
100 / 100
114 ms8792 KiB
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxN = 1e3 + 1e1;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    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<pair<int, int>> dp(1 << m);
    dp[0] = {0, 0};
    for (int msk = 0; msk < (1 << m); ++msk) {
        for (int i = 0; i < m; ++i) {
            if ((msk >> i & 1) == 0) {
                continue;
            }
            auto c = dp[msk ^ (1 << i)];
            if (c.second + b[i] == a[c.first]) {
                dp[msk] = max(dp[msk], {c.first + 1, 0});
            } else if (c.second + b[i] < a[c.first]){
                dp[msk] = max(dp[msk], {c.first, c.second + b[i]});
            }
        }
        if (dp[msk].first == n) {
            cout << "YES";
            return 0;
        }
    }
    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...