Submission #1271265

#TimeUsernameProblemLanguageResultExecution timeMemory
1271265flaming_top1Bank (IZhO14_bank)C++20
100 / 100
455 ms3128 KiB
#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 1e15;

using namespace std;

int m, n;
lint a[25], b[25];
bitset<(1 << 20) + 5> dp[21];

fami lore()
{
    SPED;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for (int i = 0; i < n; i++)
        cin >> b[i];

    for (int mask = 0; mask < (1 << n); mask++)
        dp[0][mask] = true;

    for (int mask = 1; mask < (1 << n); mask++)
    {
        lint sum = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1)
                sum += b[i];

        int idx = -1;
        for (int i = 0; i <= m; i++)
        {
            if (sum == a[i])
            {
                idx = i;
                break;
            }
        }
        if (idx != -1 and dp[idx - 1][mask] == true)
            dp[idx][mask] = true;

        for (int i = 0; i < n; i++)
            if (!(mask >> i & 1))
                for (int j = 1; j <= m; j++)
                    dp[j][mask | (1 << i)] = dp[j][mask | (1 << i)] | dp[j][mask];
    }
    cout << (dp[m][(1 << n) - 1] ? "YES" : "NO");
}
// Let your soul wander where dreams are born.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...