Submission #1342212

#TimeUsernameProblemLanguageResultExecution timeMemory
1342212PakinDioxideBank (IZhO14_bank)C++17
25 / 100
1096 ms327680 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 25, mxV = 1005;

int n, m, a[mxN], b[mxN], dp[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];
    dp[0] = 1;
    for (int idk = 1; idk <= n; idk++) {
        int DP[mxV][1<<m]; memset(DP, 0, sizeof(DP));
        for (int i = 0; i < (1 << m); i++) DP[0][i] = dp[i];
        for (int i = 1; i <= a[idk]; i++) {
            for (int kk = 0; kk < (1 << m); kk++) {
                for (int j = 0; j < m && !DP[i][kk]; j++) if (kk & (1 << j) && b[j] <= i) DP[i][kk] = max(DP[i][kk], DP[i-b[j]][kk ^ (1 << j)]);
            }
        }
        for (int i = 0; i < (1 << m); i++) dp[i] = DP[a[idk]][i];
    }
    for (int i = 0; i < (1 << m); i++) if (dp[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...