제출 #745530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745530		zjsxzy	은행 (IZhO14_bank)	C++17	100 / 100	102 ms	8636 KiB

bank

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& x: a) cin >> x;
    for (auto& x: b) cin >> x;
    vector covered(1 << m, -1), left(1 << m, -1);
    covered[0] = 0;
    left[0] = 0;
    for (int i = 0; i < (1 << m); i++) {
        if (covered[i] == -1) continue;
        int target = a[covered[i]];
        for (int j = 0; j < m; j++) {
            if (!(i >> j & 1)) {
                if (left[i] + b[j] == target && covered[i] + 1 >= covered[i | (1 << j)]) {
                    covered[i | (1 << j)] = covered[i] + 1;
                    left[i | (1 << j)] = 0;
                } else if (left[i] + b[j] < target && covered[i] >= covered[i | (1 << j)]) {
                    covered[i | (1 << j)] = covered[i];
                    left[i | (1 << j)] = left[i] + b[j];
                }
            }
        }
        if (covered[i] == n) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int ts = 1;
    // cin >> ts;
    for (int t = 1; t <= ts; t++) {
        solve();
    }
    return 0;
}

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