Submission #497501

#	Time	Username	Problem	Language	Result	Execution time	Memory
497501		vicyan1611	Bank (IZhO14_bank)	C++14	100 / 100	497 ms	96704 KiB

bank

#include <bits/stdc++.h>

using namespace std;
const int Nmax = 22;
const int Mmax = 1005;
const int Bitmax = (1 << 20);

int n, m, a[Nmax], b[Nmax], f[Nmax][Bitmax];
vector <int> tk[Mmax];

int BIT(int n, int i)
{
    return ((n >> i) & 1);
}

int trau(int i, int msk)
{
    if (i > n) return 1;
    int &res = f[i][msk];
    if (res != -1) return res;
    res = 0;
    for (auto val: tk[a[i]])
    {
        if (!(msk & val))
        {
            res = res | trau(i + 1, msk | val);
        }
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
    }
    for (int msk = 1; msk < (1 << m); ++msk)
    {
        int sum = 0;
        for (int i = 0; i < m; ++i)
        {
            if (BIT(msk, i))
            {
                sum += b[i+1];
            }
        }
        if (sum < Mmax) tk[sum].push_back(msk);
    }
    for (int i = 1; i <= n; ++i) if (tk[a[i]].size() == 0)
    {
        cout << "NO";
        return 0;
    }   
    memset(f, -1, sizeof(f));
    if (trau(1, 0)) cout << "YES"; else cout << "NO";
    return 0;
}

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