Submission #468132

#	Time	Username	Problem	Language	Result	Execution time	Memory
468132		TruaShamu	Bank (IZhO14_bank)	C++17	100 / 100	340 ms	9956 KiB

bank

#define _crt_secure_no_warnings
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
using ll = long long;


void fastio() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
}

signed main() {
    fastio();
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (auto& x : A) cin >> x;
    for (auto& x : B) cin >> x;

    vector<vector<int>> sum(20001);
    for (int mask = 0; mask < (1 << M); ++mask) {
        int cur = 0;
        for (int i = 0; i < M; ++i) {
            if (mask & (1 << i)) {
                cur += B[i];
            }
        }
        sum[cur].push_back(mask);
    }
    vector<vector<int>> dp(N + 1);
    dp[0].push_back(0);
    bool f = false;
    for (int i = 0; i < N; ++i) {
        vector<bool> vis(1 << M);
        f = false;
        for (int mask : sum[A[i]]) {
            for (int pmask : dp[i]) {
                if (!(mask & pmask) and !vis[mask | pmask]) {
                    vis[mask | pmask] = true;
                    dp[i + 1].push_back(mask | pmask);
                    f = true;
                }
            }
        }
    }
    cout << (f ? "YES\n" : "NO\n");
    return 0;
}

Compilation message (stderr)

bank.cpp:14: warning: "sz" redefined
   14 | #define sz(x) (int)x.size()
      | 
bank.cpp:8: note: this is the location of the previous definition
    8 | #define sz(x) (int) (x).size()
      |

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