Submission #751921

#	Time	Username	Problem	Language	Result	Execution time	Memory
751921		benjaminkleyn	Bank (IZhO14_bank)	C++17	100 / 100	179 ms	8544 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;

int n, m, a[20], b[20];
pair<int, int> dp[1 << 20];
// dp[mask] = {number of people paid with these notes, auxiliary coins left over}.

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];

    dp[0] = {0, 0};
    for (uint mask = 1; mask < (1 << m); mask++)
    {
        dp[mask] = {0, 0};
        for (int i = 0; i < m; i++)
            if (mask & (1 << i))
                dp[mask].second += b[i];

        for (int i = 0; i < m; i++)
            if (mask & (1 << i))
            {
                auto [num, aux] = dp[mask ^ (1 << i)];
                dp[mask] = max(dp[mask], make_pair(num + (aux + b[i] == a[num]), (aux + b[i]) * (aux + b[i] != a[num])));
            }

        if (dp[mask].first == n)
            return cout << "YES\n", 0;
    }
    cout << "NO\n";

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:21:30: warning: comparison of integer expressions of different signedness: 'uint' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   21 |     for (uint mask = 1; mask < (1 << m); mask++)
      |                         ~~~~~^~~~~~~~~~

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