제출 #972595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972595		kfhjad	은행 (IZhO14_bank)	C++17	100 / 100	78 ms	8636 KiB

bank

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int dp[1 << 20][2]; // upto person, sum
int people[20], notes[20];

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
        cin >> people[i];
    
    for (int i = 0; i < M; ++i)
        cin >> notes[i];
    
    int p, sum;
    
    for (int mask = 1; mask < (1 << M); ++mask)
    {
        bool worked = false;

        for (int i = 0; i < M; ++i)
        {
            if (mask & (1 << i))
            {
                if (dp[mask ^ (1 << i)][0] == -1)
                    continue;
                
                p = dp[mask ^ (1 << i)][0];
                sum = dp[mask ^ (1 << i)][1];

                if (sum + notes[i] < people[p])
                {
                    dp[mask][0] = p;
                    dp[mask][1] = sum + notes[i];
                    worked = true;
                    break;
                }
                else if (sum + notes[i] == people[p])
                {
                    dp[mask][0] = p + 1;
                    dp[mask][1] = 0;
                    worked = true;

                    if (dp[mask][0] == N)
                    {
                        cout << "YES\n";
                        return 0;
                    }
                    break;
                }
            }
        }

        if (!worked)
            dp[mask][0] = -1;
    }

    cout << "NO\n";
    
    return 0;
}

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