제출 #1326158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326158		pfang	은행 (IZhO14_bank)	C++20	0 / 100	1 ms	332 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);
    long long sum_a = 0, sum_b = 0;

    for(int i = 0; i < N; i++){
        cin >> a[i];
        sum_a += a[i];
    }

    for(int i = 0; i < M; i++){
        cin >> b[i];
        sum_b += b[i];
    }

    // Necessary condition
    if(sum_a != sum_b){
        cout << "NO";
        return 0;
    }

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

    // Precompute subset sums
    vector<int> sum(1 << M, 0);
    for(int mask = 1; mask < (1 << M); mask++){
        int l = mask & -mask;
        int j = __builtin_ctz(l);
        sum[mask] = sum[mask ^ l] + b[j];
    }

    vector<int> dp(1 << M, -1);
    dp[0] = 0;

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

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

        int current_sum = sum[mask];
        int filled = current_sum - pref[k];

        for(int j = 0; j < M; j++){
            if(!(mask & (1 << j))){
                int next_fill = filled + b[j];
                if(next_fill > a[k]) continue;

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

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

    // Since total sums match, we must use all notes
    int full_mask = (1 << M) - 1;
    cout << (dp[full_mask] == N ? "YES" : "NO");

    return 0;
}

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