Submission #1342219

#TimeUsernameProblemLanguageResultExecution timeMemory
1342219PakinDioxideBank (IZhO14_bank)C++17
100 / 100
433 ms60368 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 21;

int n, m, a[mxN], b[mxN], dp[mxN+1][1<<mxN];
vector <vector <bool>> vis(mxN, vector <bool> (1 << mxN));

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    vis[0][0] = 1;
    for (int k = 1; k < (1 << m); k++) {
        for (int j = 0; j < m; j++) if (k & (1 << j)) {
            for (int i = 1; i <= n; i++) {
                if (vis[i][k ^ (1 << j)] || (vis[i-1][k ^ (1 << j)] && dp[i-1][k ^ (1 << j)] == a[i-1])) {
                    if (dp[i][k ^ (1 << j)] + b[j] > a[i]) continue;
                    dp[i][k] = dp[i][k ^ (1 << j)] + b[j];
                    vis[i][k] = 1;
                    if (i == n && dp[i][k] == a[i]) { cout << "YES\n"; return 0; }
                }
            }
        }
    }
    cout << "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...