Submission #1326159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326159		pfang	Bank (IZhO14_bank)	C++20	100 / 100	85 ms	8532 KiB

bank

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

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

    int N, M;
    cin >> N >> M;

    vector<int> a(N), b(M);
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < M; i++) cin >> b[i];

    // Precompute subset sums of banknotes
    int total_masks = 1 << M;
    vector<int> subset_sum(total_masks, 0);

    for(int mask = 1; mask < total_masks; mask++){
        int lowest_bit = mask & -mask;
        int index = __builtin_ctz(lowest_bit);
        subset_sum[mask] = subset_sum[mask ^ lowest_bit] + b[index];
    }

    // Prefix sums of salaries
    vector<int> prefix(N + 1, 0);
    for(int i = 0; i < N; i++){
        prefix[i + 1] = prefix[i] + a[i];
    }

    // dp[mask] = number of fully paid people
    vector<int> dp(total_masks, -1);
    dp[0] = 0;

    for(int mask = 0; mask < total_masks; mask++){
        if(dp[mask] == -1) continue;

        int paid_people = dp[mask];
        if(paid_people == N) continue;

        int current_total = subset_sum[mask];
        int current_fill = current_total - prefix[paid_people];

        for(int j = 0; j < M; j++){
            if(mask & (1 << j)) continue;

            int next_fill = current_fill + b[j];
            if(next_fill > a[paid_people]) continue;

            int new_mask = mask | (1 << j);

            if(next_fill == a[paid_people])
                dp[new_mask] = max(dp[new_mask], paid_people + 1);
            else
                dp[new_mask] = max(dp[new_mask], paid_people);
        }
    }

    // Same final check as original
    for(int mask = 0; mask < total_masks; mask++){
        if(dp[mask] == N){
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
    return 0;
}

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