Submission #1316724

#TimeUsernameProblemLanguageResultExecution timeMemory
1316724chikien2009Bank (IZhO14_bank)C++20
71 / 100
1097 ms10164 KiB
#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const int maxn = 2e4 + 1;

int n, m;
int a[20], b[20];
bool appear[1 << 20], cur[1 << 20];
vector<int> mask[maxn];

int main()
{
    setup();

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        a[i] += (i == 0 ? 0 : a[i - 1]);
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> b[i];
    }
    for (int i = 0, j; i < (1 << m); ++i)
    {
        j = 0;
        for (int k = 0; k < m; ++k)
        {
            j += ((i >> k) & 1) * b[k];
        }
        mask[j].push_back(i);
    }
    appear[0] = 1;
    for (int i = 1, j = 0; i < maxn && j < n; ++i)
    {
        fill_n(cur, 1 << 20, 0);
        for (auto &k : mask[i])
        {
            for (int h = 0; h < m; ++h)
            {
                if (((k >> h) & 1) && appear[k - (1 << h)])
                {
                    cur[k] |= appear[k - (1 << h)];
                }
            }
        }
        if (i == a[j])
        {
            fill_n(appear, 1 << 20, 0);
            j++;
        }
        for (int k = 0; k < (1 << 20); ++k)
        {
            appear[k] |= cur[k];
        }
    }
    cout << ((*max_element(appear, appear + (1 << m))) == 0 ? "NO" : "YES");
    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...