Submission #679112

#TimeUsernameProblemLanguageResultExecution timeMemory
679112borisAngelovBank (IZhO14_bank)C++17
71 / 100
1089 ms35868 KiB
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 25;
const int max_mask = (1 << 20) + 5;

int n, m;

int a[maxn];
int b[maxn];

vector<int> byMasks[maxn * 1000];

bool dp[maxn][max_mask];
bool is_calculated[maxn][max_mask];

bool check(int mask, int new_mask)
{
    for (int i = 0; i < 20; ++i)
    {
        bool bit1 = false;

        if ((mask & (1 << i)) != 0)
        {
            bit1 = true;
        }

        bool bit2 = false;

        if ((new_mask & (1 << i)) != 0)
        {
            bit2 = true;
        }

        if (bit1 == true && bit2 == true) return false;
    }

    return true;
}

bool f(int pos, int mask)
{
    if (pos == n) return true;

    if (is_calculated[pos][mask] == true) return dp[pos][mask];
    is_calculated[pos][mask] = true;

    bool result = false;

    for (auto curr_mask : byMasks[a[pos]])
    {
        if (check(mask, curr_mask) == false) continue;
        result = (result | (f(pos + 1, (mask | curr_mask))));
    }

    return dp[pos][mask] = result;
}

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

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 0; i < m; ++i)
    {
        cin >> b[i];
    }

    for (int mask = 0; mask < (1 << m); ++mask)
    {
        int curr_sum = 0;

        for (int i = 0; i < m; ++i)
        {
            if ((mask & (1 << i)) != 0)
            {
                curr_sum += b[i];
            }
        }

        byMasks[curr_sum].push_back(mask);
    }

    for (int i = 0; i < n; ++i)
    {
        if (byMasks[a[i]].empty())
        {
            cout << "NO\n";
            return 0;
        }
    }

    if (f(0, 0) == true)
    {
        cout << "YES\n";
    }
    else
    {
        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...