Submission #495827

#	Time	Username	Problem	Language	Result	Execution time	Memory
495827		ryangohca	Bank (IZhO14_bank)	C++17	100 / 100	571 ms	164768 KiB

bank

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
#define int long long
// Do you remember, the fireworks back then?  ~ YooA, Remember Me
using namespace std;
int dp[20][1<<20];
int arr[20], val[20];
unordered_map<int, vector<int>> mp;
int n, m;
bool f(int x, int bm){
    if (x == n) return true;
    if (dp[x][bm] != -1) return dp[x][bm];
    bool ans = false;
    for (auto i : mp[arr[x]]){
        if ((i & bm) == 0) ans |= f(x+1, bm | i);
    }
    return dp[x][bm] = ans;
}
main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        mp[arr[i]];
    }
    for (int i = 0; i < m; i++) cin >> val[i];
    for (int i = 1; i < (1<<m); i++){
        int s = 0;
        for (int j = 0; j < m; j++){
            if (i & (1 << j)) s += val[j];
        }
        if (mp.find(s) != mp.end()) mp[s].push_back(i);
    }
    bool ans = f(0, 0);
    cout << (ans ? "YES" : "NO") << '\n';
}

Compilation message (stderr)

bank.cpp: In function 'bool f(long long int, long long int)':
bank.cpp:19:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   19 |     return dp[x][bm] = ans;
      |            ~~~~~~~~~~^~~~~
bank.cpp: At global scope:
bank.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

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