Submission #930357

#	Time	Username	Problem	Language	Result	Execution time	Memory
930357		uped	Bank (IZhO14_bank)	C++14	52 / 100	1051 ms	33776 KiB

bank

#include <bits/stdc++.h>

#define DEBUG(x) cout << #x << ": " << x << '\n';

using namespace std;
using ll = long long;

set<tuple<int, int, int>> visited;

const int MAX = 20;
int a[MAX + 1];
int b[MAX];
int n, m;

void solve(int idx, int val, int mask) {
    if (visited.count({idx, val, mask})) return;
    visited.emplace(idx, val, mask);
    if (idx == n) return;
    for (int i = 0; i < m; ++i) {
        if (mask & (1 << i)) continue;
        if (val - b[i] == 0) {
            solve(idx + 1, a[idx + 1], mask | (1 << i));
        } else if (val - b[i] > 0) {
            solve(idx, val - b[i], mask | (1 << i));
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    solve(0, a[0], 0);
    bool ans = false;
    for (int i = 0; i < (1 << m); ++i) {
        if (visited.count({n, 0, i})) {
            ans = true;
            break;
        }
    }
    cout << (ans ? "YES" : "NO");
}

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