Submission #550574

#TimeUsernameProblemLanguageResultExecution timeMemory
550574AlexandruabcdeBank (IZhO14_bank)C++14
0 / 100
1084 ms640 KiB
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 21;

bool dp[NMAX][(1<<NMAX)];

int N, M;
int A[NMAX], B[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= N; ++ i )
        cin >> A[i];

    for (int i = 1; i <= M; ++ i )
        cin >> B[i];
}

void Solve () {
    dp[0][0] = true;
    for (int i = 1; i <= N; ++ i ) {
        vector <int> posib;
        for (int j = 0; j < (1<<M); ++ j ) {
            int sum = 0;
            for (int k = 0; k < M; ++ k )
                if ((j&(1<<k))) sum += B[k];

            if (sum == A[i])
                posib.push_back(j);
        }

        for (int mask = 0; mask < (1<<M); ++ mask ) {
            for (auto it : posib) {
                if ((mask&it) != it) continue;

                dp[i][mask] |= dp[i-1][(mask^it)];
            }
        }
    }

    bool ans = false;
    for (int mask = 0; mask < (1<<M); ++ mask )
        ans |= dp[N][mask];

    cout << (ans == true ? "YES" : "NO") << '\n';
}

int main () {
    Read();
    Solve();

    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...