Submission #1272664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272664		osmiyum	Bank (IZhO14_bank)	C++20	19 / 100	73 ms	8520 KiB

bank

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if (!(cin >> N >> M)) return 0;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    vector<int> b(M);
    for (int i = 0; i < M; ++i) cin >> b[i];

    // prefix sums of salaries
    vector<int> pref(N+1, 0);
    for (int i = 0; i < N; ++i) pref[i+1] = pref[i] + a[i];
    int FULL = 1<<M;

    // sum[mask] : toplam değer
    vector<int> sum(FULL, 0);
    for (int mask = 1; mask < FULL; ++mask) {
        int lsb = __builtin_ctz(mask); // en düşük 1 bit pozisyonu
        int pmask = mask ^ (1<<lsb);
        sum[mask] = sum[pmask] + b[lsb];
    }

    // dp[mask] = -1 unreachable, otherwise currently paid amount to current person (0..a[cur]-1 or 0..a[cur])
    vector<int> dp(FULL, -1);
    dp[0] = 0;

    for (int mask = 0; mask < FULL; ++mask) {
        if (dp[mask] < 0) continue;
        // kaç kişinin maaşı tamamlanmış?
        int S = sum[mask];
        // upper_bound -> ilk pref > S, onun bir eksiği pref[t] <= S
        int ub = int(upper_bound(pref.begin(), pref.end(), S) - pref.begin());
        int cur = ub - 1; // cur kişiler tamamlandı
        if (cur == N) { // hepsi ödenmiş
            cout << "YES\n";
            return 0;
        }
        int paid = dp[mask]; // şu anki kişiye ödenmiş miktar = S - pref[cur]
        // deneyelim hangi banknotu ekleyebiliriz
        for (int j = 0; j < M; ++j) if (!(mask & (1<<j))) {
            int need = a[cur];
            if (paid + b[j] <= need) {
                int nm = mask | (1<<j);
                dp[nm] = max(dp[nm], paid + b[j]);
            }
        }
    }

    // hiçbiri tüm maaşları ödeyemedi
    cout << "NO\n";
    return 0;
}

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