Submission #1282524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282524		dang_hai_long	은행 (IZhO14_bank)	C++20	71 / 100	1096 ms	31216 KiB

bank

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

int N, M;
vector<int> a;
vector<int> b;
vector<int> a_sorted;
vector<ll> sumMask;
vector<vector<unsigned char>> visited;

bool dfs(int mask, int idx) {
    if (idx == (int)a_sorted.size()) return true;
    if (visited[idx][mask]) return false;
    ll sumRemain = 0;
    for (int i = idx; i < (int)a_sorted.size(); ++i) sumRemain += a_sorted[i];
    if (sumMask[mask] < sumRemain) { visited[idx][mask] = 1; return false; }
    int need = a_sorted[idx];
    if (need > sumMask[mask]) { visited[idx][mask] = 1; return false; }

    int sub = mask;
    if (need == 0) {
        if (dfs(mask, idx+1)) return true;
        visited[idx][mask] = 1;
        return false;
    }

    while (true) {
        if (sumMask[sub] == need) {
            if (dfs(mask ^ sub, idx + 1)) return true;
        }
        if (sub == 0) break;
        sub = (sub - 1) & mask;
    }
    visited[idx][mask] = 1;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> M)) return 0;
    a.assign(N, 0);
    b.assign(M, 0);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < M; ++i) cin >> b[i];

    ll sumA = 0;
    for (int x: a) sumA += x;
    ll sumB = 0;
    for (int x: b) sumB += x;
    if (sumA > sumB) { cout << "NO\n"; return 0; }

    a_sorted = a;
    sort(a_sorted.rbegin(), a_sorted.rend());

    int LIM = 1 << M;
    sumMask.assign(LIM, 0);
    for (int mask = 1; mask < LIM; ++mask) {
        int lsb = __builtin_ctz(mask);
        int prev = mask ^ (1 << lsb);
        sumMask[mask] = sumMask[prev] + b[lsb];
    }

    visited.assign(N+1, vector<unsigned char>(LIM, 0));

    bool ok = dfs((1<<M)-1, 0);
    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

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