제출 #1325598

#제출 시각아이디문제언어결과실행 시간메모리
1325598rainy3218은행 (IZhO14_bank)C++20
0 / 100
1 ms332 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 l = i & -i;
        int j = __builtin_ctz(l);
        sum[i] = sum[i ^ l] + 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 s = sum[i];
        int c = s - p[k];

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

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

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

    for (int i = 0; i < (1 << M); i++)
        if (dp[i] == N) {
            cout << "YES";
            return 0;
        }

    cout << "NO";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...