제출 #679118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679118		borisAngelov	Bank (IZhO14_bank)	C++11	100 / 100	481 ms	36212 KiB

bank

#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 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 ((mask & curr_mask) != 0) 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;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29