제출 #1268222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268222		puc_player	은행 (IZhO14_bank)	C++20	100 / 100	344 ms	3200 KiB

bank

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> salary;
vector<int> banknotes;
vector<vector<bool>> dp;
vector<vector<int>> candidates;

bool canAssign(int i, int mask)
{
    if (i == N)
    {
        return true;
    }
    if (dp[i][mask] != -1)
        return dp[i][mask];
    for (int &c : candidates[i])
    {
        if (!(mask & c))
        {
            if (canAssign(i + 1, mask | c))
                return dp[i][mask] = true;
        }
    }
    return dp[i][mask] = false;
}

int main()
{
    cin >> N >> M;
    salary.resize(N);
    banknotes.resize(M);

    for (int i = 0; i < N; ++i)
        cin >> salary[i];
    for (int i = 0; i < M; ++i)
        cin >> banknotes[i];

    dp.resize(N + 1, vector<bool>(1 << M, false));
    candidates.resize(N);

    int m = 1 << M;
    for (int mask = 0; mask < m; mask++)
    {
        int sum = 0;
        for (int i = 0; i < M; i++)
        {
            if (mask & (1 << i))
                sum += banknotes[i];
        }
        for (int i = 0; i < N; i++)
        {
            if (sum == salary[i])
                candidates[i].push_back(mask);
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < N; i++)
    {
        for (int mask = 0; mask < m; mask++)
        {
            if (dp[i][mask])
            {
                for (int &c : candidates[i])
                {
                    if (!(mask & c))
                    {
                        dp[i + 1][mask | c] = true;
                    }
                }
            }
        }
    }
    bool ans = false;
    for (int i = 0; i < (1 << M); i++)
    {
        if (dp[N][i])
        {
            ans = true;
            break;
        }
    }
    cout << (ans ? "YES" : "NO");
    return 0;
}

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