Submission #978952

#	Time	Username	Problem	Language	Result	Execution time	Memory
978952		Ska	Bank (IZhO14_bank)	C++14	100 / 100	76 ms	8792 KiB

bank

#include <bits/stdc++.h>
using namespace std;

const int N = 20;

int n, m;
int a[N], b[N];
pair<int, int> f[1 << N];

void solve() {
    for (int mask = 1; mask <= 1 << m; ++mask) {
        bool ok = false;
        for (int i = 0; i < m; ++i) {
            if ((mask >> i & 1) == 0) {
                continue;
            }
            int prev = mask ^ 1 << i;
            if (f[prev].first == -1) {
                continue;
            }
            if (f[prev].second + b[i] < a[f[prev].first]) {
                f[mask] = {f[prev].first, f[prev].second + b[i]};
                ok = true;
                break;
            } else if (f[prev].second + b[i] == a[f[prev].first]) {
                f[mask] = {f[prev].first + 1, 0};
                if (f[mask].first == n) {
                    cout << "YES\n";
                    return;
                }
                ok = true;
                break;
            }
        }
        if (!ok) {
            f[mask].first = -1;
        }
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    solve();
}

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