Submission #978955

#	Time	Username	Problem	Language	Result	Execution time	Memory
978955		Ska	Bank (IZhO14_bank)	C++14	0 / 100	1 ms	348 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];

bool backtrack(int mask, int idx, int sum, int lb, int ub) {
    if (idx == n) {
        return true;
    }
    bool first = false;
    for (int i = lb; i < ub; ++i) {
        if ((mask >> i & 1) == 0) {
            continue;
        }
        if (!first) {
            first = true;
            lb = i;
        }
        if (sum + b[i] < a[idx] && backtrack(mask | 1 << i, idx, sum + b[i], lb + (i == lb), ub - (i == ub - 1))) {
            return true;
        }
        if (sum + b[i] == a[idx] && backtrack(mask | 1 << i, idx + 1, 0, lb + (i == lb), ub - (i == ub - 1))) {
            return true;
        }
    }
    return false;
}

// 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();
    if (backtrack(0, 1, 0, 0, m)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

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