Submission #519516

#	Time	Username	Problem	Language	Result	Execution time	Memory
519516		danikoynov	Bank (IZhO14_bank)	C++14	100 / 100	92 ms	8516 KiB

bank

#include<bits/stdc++.h>

using namespace std;
const int maxn = 21;

int n, m, a[maxn], b[maxn], cov[(1 << maxn)], lef[(1 << maxn)];
vector < int > g[maxn];
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    for (int i = 0; i < m; i ++)
        cin >> b[i];

    cov[0] = 1;
    lef[0] = a[1];
    for (int mask = 1; mask < (1 << m); mask ++)
    {

        for (int bit = 0; bit < m; bit ++)
        {
            if ((mask & (1 << bit)) == 0)
                continue;

            int old_mask = (mask ^ (1 << bit));
            int wcov = cov[old_mask];
            int wlef = lef[old_mask] - b[bit];
            if (wlef < 0)
                continue;
            if (wlef == 0)
                wcov ++, wlef = a[wcov];
            if (wcov > cov[mask])
            {
                cov[mask] = wcov;
                lef[mask] = wlef;
            }

        }

        if (cov[mask] > n)
        {
            cout << "YES" << endl;
            return;
        }
    }

    cout << "NO" << endl;
}
int main()
{
    solve();
	return 0;
}

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