제출 #1325596

#제출 시각아이디문제언어결과실행 시간메모리
1325596rainy3218은행 (IZhO14_bank)C++20
100 / 100
84 ms8612 KiB
#include <bits/stdc++.h>
using namespace std;

int a[25];
int b[25];

int p[25];

int main() {
    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];

    vector<int> sum(1 << M, 0);
    for (int i = 1; i < (1 << M); i++) {
        int lsb = i & -i;
        int j = __builtin_ctz(lsb);
        sum[i] = sum[i ^ lsb] + b[j];
    }

    for (int i = 0; i < N; i++) p[i + 1] = p[i] + a[i];

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


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

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

        int used_sum = sum[i];
        int current_paid = used_sum - p[k];

        for (int j = 0; j < M; j++) {
            if (!(i & (1 << j))) {
                int new_paid = current_paid + b[j];
                if (new_paid > a[k]) continue;

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

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

    bool ans = false;
    for (int i = 0; i < (1 << M); i++)
        if (dp[i] == N)
            ans = true;

    cout << (ans ? "YES\n" : "NO\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...