Submission #535737

#TimeUsernameProblemLanguageResultExecution timeMemory
535737nhquanBank (IZhO14_bank)C++17
71 / 100
1086 ms86732 KiB
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define ii pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
#define sz(a) (int)a.size()

#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, a, b) for (int i = a; i >= b; --i)

#define ll long long

#define oo 1000000007
#define maxN 21
#define maxM 21

using namespace std;

int n, m, a[maxN], b[maxM];
int f[maxN][(1 << maxN)];

int getBit(int i, int x) {
    return (x >> i) & 1;
}

int dp(int i, int S) {
    if (!i) return 1;
    if (f[i][S] != -1) return f[i][S];
    for (int T = S; T; T = (T-1)&S) {
        int tmp = 0;
        fto(j, 0, m-1) {
            if (getBit(j, T)) tmp += b[j+1];
        }
        if (tmp == a[i] && dp(i-1, S^T)) return f[i][S] = 1;
    }
    return f[i][S] = 0;
}

int main() {

    cin >> n >> m;
    fto(i, 1, n) {
        cin >> a[i];
    }

    fto(i, 1, m) {
        cin >> b[i];
    }

    fto(i, 0, n) {
        fto(S, 0, (1 << m)-1) {
            f[i][S] = -1;
        }
    }

    /*fto(S, 0, (1 << m)-1) {
        if (dp(n, S)) {
            cout << "YES\n";
            return 0;
        }
    }*/

    if (dp(n, (1 << m)-1)) {
        cout << "YES\n";
        return 0;
    }

    cout << "NO\n";

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