Submission #1074654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074654		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	705 ms	219460 KiB

bank

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(a) (int)(a).size()
#define el '\n'
#define F first
#define S second
#define For(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define Rof(i, a, b) for (int i = (a); i >= (int)(b); i--)
#define Fore(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)

using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vii = vector<pii>;

//*** START CODING ***//
int setBit(int n, int pos) { return n |= (1 << pos); }
int clearBit(int n, int pos) { return n &= ~(1 << pos); }
int getBit(int n, int pos) { return (n >> pos) & 1; }
int toggleBit(int n, int pos) { return n ^= (1 << pos); }

const long long oo = 2e18, mod = 1e9 + 7;
const int ms = 20 + 5;
int n, m;
int a[ms], b[ms];

vvi memo;
map<int, vi> sumMask;

bool f(int mask, int idx) {
    if (idx == n) return true;
    if (memo[mask][idx] != -1) return memo[mask][idx];
    bool ans = false;
    for (auto msk : sumMask[a[idx]]) {
        if (msk & mask) continue;
        ans |= f(mask | msk, idx + 1);
    }

    return memo[mask][idx] = ans;
};

void solve() {
    cin >> n >> m;
    For(i, 0, n - 1) cin >> a[i];
    For(i, 0, m - 1) cin >> b[i];

    memo = vvi(1 << m, vi(n, -1));
    for (int mask = 0; mask < (1LL << m); mask++) {
        int sum = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                sum += b[i];
            }
        }
        sumMask[sum].pb(mask);
    }

    bool ans = f(0, 0);

    if (ans)
        cout << "YES" << el;
    else
        cout << "NO" << el;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool f(long long int, long long int)':
bank.cpp:48:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   48 |     return memo[mask][idx] = ans;

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