Submission #1115811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115811		nanghongg	Bank (IZhO14_bank)	C++14	19 / 100	68 ms	4568 KiB

bank

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define ll long long
#define ld long double

#define PI 3.1415926535897932384626433832795l;

int a[21];
bool dp[2][1 << 21];

void solve() {
    int n, m;
    cin >> n >> m;

    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }

    vector<vector<int>> valid_masks(1001);
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];
    for (int mask = 0; mask < (1 << m); mask++) {
        int sum = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) sum += b[i];
        }
        if (mp.count(sum)) valid_masks[sum].push_back(mask);
    }

    if (n == 1 && !valid_masks[a[1]].empty()) {
        cout << "YES\n";
        return;
    }

    memset(dp, false, sizeof(dp));
    dp[0][0] = true;

    for (int i = 1; i <= n; i++) {
        int cur = i % 2, prev = 1 - cur;
        memset(dp[cur], false, (1 << m) * sizeof(bool));

        for (int mask = 0; mask < (1 << m); mask++) {
            if (!dp[prev][mask]) continue;
            for (int can_mask : valid_masks[a[i]]) {
                if ((mask & can_mask) != can_mask) continue;
                dp[cur][mask ^ can_mask] = true;
            }
        }
    }
    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[n % 2][mask]) {
            cout << "YES\n";
            return;
        }
    }

    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

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