제출 #1271265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271265		flaming_top1	은행 (IZhO14_bank)	C++20	100 / 100	455 ms	3128 KiB

bank

#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.

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