Submission #1325526

#TimeUsernameProblemLanguageResultExecution timeMemory
1325526askewwBank (IZhO14_bank)C++20
100 / 100
158 ms12716 KiB
#include <bits/stdc++.h>
using namespace std;

template<typename T>
using V = vector<T>;
using pi  = pair<int, int>;

const int INF = 1e9;

int n, m;
V<int> a, b;
V<pi> sm;
V<int> dp;

int main() {
    cin >> n >> m;

    a.resize(n); b.resize(m);
    for (auto& i : a) cin >> i;
    for (auto& i : b) cin >> i;

    sm = V<pi>(1 << m);
    for (int S = 0; S < (1 << m); S++) {
        int s = 0;
        for (int i = 0; i < m; i++) {
            if (S & (1 << i)) s += b[i];
        }
        int c = 0, j = 0;
        bool f = false;
        for (int i = 0; i < n; i++) {
            c += a[i];
            if (c > s) {
                f = true;
                j = i;
                break;
            }
        }

        if (f) {
            sm[S] = {j, s - (c - a[j])};
        } else {
            if (c == s) sm[S] = {n, 0};
            else sm[S] = {-1, -1};
        }
    }

    dp = V<int>(1 << m);
    dp[0] = 1;
    for (int S = 0; S < (1 << m); S++) {
        if (sm[S] == pi{-1, -1}) continue;

        for (int i = 0; i < m; i++) {
            if (S & (1 << i)) {
                int s = S ^ (1 << i);
                pi p = sm[s];
                if (p.second + b[i] > a[p.first]) continue;
                p.second += b[i];
                if (p.second == a[p.first]) {
                    p.first++;
                    p.second = 0;
                }

                dp[S] |= dp[s];
            }
        }

        if (sm[S] == pi{n, 0} && dp[S]) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...