Submission #660160

#	Time	Username	Problem	Language	Result	Execution time	Memory
660160		Alma	Bank (IZhO14_bank)	C++17	100 / 100	121 ms	8576 KiB

bank

#include <bits/stdc++.h>
using namespace std;
 
int N, M;
int a[20], b[20], pre[20];
int idx[(1 << 20)], dp[(1 << 20)];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    memset(pre, 0, sizeof pre);
    memset(dp, -1, sizeof dp);
    memset(idx, -1, sizeof idx);
    dp[0] = idx[0] = 0;
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (i == 0) pre[i] = a[i];
        else pre[i] = a[i] + pre[i-1];
    }
    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))) continue;
            int x = mask - (1 << i);
            if (dp[x] == -1 or idx[x] == -1) continue;
            
            if (dp[x] == pre[idx[x]]) {
                dp[mask] = dp[x] + b[i];
                idx[mask] = idx[x] + 1;
            }
            if (dp[x] + b[i] <= pre[idx[x]]) {
                dp[mask] = dp[x] + b[i];
                idx[mask] = idx[x];
            }
        }
    }
 
    for (int mask = 0; mask < (1 << M); mask++) {
        if (dp[mask] == pre[N-1] and idx[mask] == N-1) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
 
    return 0;
}

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