Submission #1245151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245151		datluong_04	은행 (IZhO14_bank)	C++20	100 / 100	168 ms	18344 KiB

bank

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

int N, M;
vector<int> A;
vector<int> B;
vector<ll> sum_mask;
unordered_map<int, vector<int>> mp;  // mp[tổng] = list các mask cho tổng đó
vector<ll> suf_sum;                  // tổng lương từ idx đến N-1
vector<unordered_map<int,char>> memo;

bool dfs(int idx, int avail) {
    if (idx == N) return true;
    if (memo[idx].count(avail)) return memo[idx][avail];
    // Prune: tổng tiền còn lại phải >= tổng lương còn lại
    ll rem_money = sum_mask[avail];
    if (rem_money < suf_sum[idx]) {
        return memo[idx][avail] = false;
    }
    int need = A[idx];
    auto it = mp.find(need);
    if (it == mp.end()) {
        return memo[idx][avail] = false;
    }
    for (int sub : it->second) {
        if ((sub & avail) != sub) continue;
        int next_avail = avail ^ sub;
        if (dfs(idx + 1, next_avail)) {
            return memo[idx][avail] = true;
        }
    }
    return memo[idx][avail] = false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    A.resize(N);
    B.resize(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];

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

    // Tính sum_mask
    int FULL = 1 << M;
    sum_mask.assign(FULL, 0);
    for (int mask = 1; mask < FULL; mask++) {
        int b = __builtin_ctz(mask);
        int prev = mask ^ (1 << b);
        sum_mask[mask] = sum_mask[prev] + B[b];
    }
    // Nhóm lại theo tổng
    for (int mask = 0; mask < FULL; mask++) {
        mp[ sum_mask[mask] ].push_back(mask);
    }

    // Sắp lương giảm dần và tính suffix sum
    sort(A.rbegin(), A.rend());
    suf_sum.assign(N+1, 0);
    for (int i = N-1; i >= 0; i--) {
        suf_sum[i] = suf_sum[i+1] + A[i];
    }

    memo.assign(N, unordered_map<int,char>());
    bool ok = dfs(0, FULL - 1);
    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

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