제출 #1268217

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

bank

#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> salary;
vector<int> banknotes;
vector<vector<int>> 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, vector<int>(1 << M, -1));
    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);
        }
    }
    cout << (canAssign(0, 0) ? "YES" : "NO");
    return 0;
}

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