Submission #659285

#	Time	Username	Problem	Language	Result	Execution time	Memory
659285		KING	Bank (IZhO14_bank)	C++14	100 / 100	581 ms	58884 KiB

bank

#include<bits/stdc++.h>
#define NOT_STONKS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;
const int maxn = 21; //4e6 + 10; //3e5 + 10;
const int mod = 1e9 + 7; //998244353;
typedef long long ll;

int sum[(1 << maxn) + 5], psum[maxn], dp[maxn][(1 << maxn) + 5], n, m, a[maxn], b[maxn];
vector<int> vec[maxn + 5];
int main() {
    NOT_STONKS;
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    for (int mask = 1; mask < (1 << m); mask++) 
        for (int i = 0; i < m; i++) if (mask & (1 << i)) 
            sum[mask] += b[i];
    for (int i = 0; i < n; i++) 
        for (int mask = 1; mask < (1 << m); mask++) 
            if (sum[mask] == a[i]) vec[i].push_back(mask);
    
    psum[0] = a[0];
    for (int i = 1; i < n; i++) psum[i] = psum[i - 1] + a[i];
    for (int mask : vec[0]) dp[0][mask] = true;

    for (int i = 1; i < n; i++) {
        for (int mask = 1; mask < (1 << m); mask++) {
            if (sum[mask] != psum[i]) continue;
            for (int smask : vec[i]) if ((smask & mask) == smask) {
                dp[i][mask] |= dp[i - 1][mask ^ smask];
            }
        }
    }
    bool ok = false;
    for (int mask = 1; mask < (1 << m); mask++)
        ok |= dp[n - 1][mask];
    (ok) ? (cout << "YES") : (cout << "NO");
    return 0;
}

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