Submission #1189690

#TimeUsernameProblemLanguageResultExecution timeMemory
1189690JomnoiBank (IZhO14_bank)C++17
25 / 100
1095 ms680 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 25;
const int MAX_R = 1<<20;

int a[MAX_N], b[MAX_N];
bool dp[MAX_N][MAX_R];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

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

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

    dp[0][0] = true;
    for (int i = 0; i < N; i++) {
        for (int bit = 0; bit < (1<<M); bit++) {
            vector <int> remain;
            for (int j = 0; j < M; j++) {
                if (!(bit & (1<<j))) {
                    remain.push_back(j);
                }
            }
            for (int b2 = 0; b2 < (1<<remain.size()); b2++) {
                int sum = 0, bit2 = 0;
                for (int k = 0; k < remain.size(); k++) {
                    if (b2 & (1<<k)) {
                        sum += b[remain[k]];
                        bit2 |= (1<<remain[k]);
                    }
                }
                if (dp[i][bit] && sum == a[i]) dp[i + 1][bit | bit2] = true;
            }
        }
    }

    bool ok = false;
    for (int bit = 0; bit < (1<<M); bit++) {
        if (dp[N][bit]) ok = true;
    }

    if (ok) cout << "YES";
    else 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...