Submission #887480

#	Time	Username	Problem	Language	Result	Execution time	Memory
887480		Perl32	Bank (IZhO14_bank)	C++14	100 / 100	114 ms	8792 KiB

bank

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

/*

 */

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