Submission #645603

#	Time	Username	Problem	Language	Result	Execution time	Memory
645603		finn__	Bank (IZhO14_bank)	C++17	100 / 100	101 ms	16724 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int main()
{
    size_t n, m;
    cin >> n >> m;

    vector<unsigned> sal(n), banknotes(m);
    for (unsigned &x : sal)
        cin >> x;
    for (unsigned &x : banknotes)
        cin >> x;

    vector<pair<size_t, unsigned>> dp(1 << m, {0, 0});

    for (unsigned s = 0; s < 1 << m; s++)
    {
        for (unsigned i = 0; i < m; i++)
        {
            if (s & (1 << i))
            {
                if (dp[s ^ (1 << i)].first == n)
                    dp[s] = {n, 0};
                else if (dp[s ^ (1 << i)].second + banknotes[i] == sal[dp[s ^ (1 << i)].first] &&
                         dp[s ^ (1 << i)].first + 1 > dp[s].first)
                    dp[s] = {dp[s ^ (1 << i)].first + 1, 0};
                else if (dp[s ^ (1 << i)].first >= dp[s].first)
                    dp[s] = {dp[s ^ (1 << i)].first, dp[s ^ (1 << i)].second + banknotes[i]};
            }
        }
    }

    cout << (dp[(1 << m) - 1].first == n ? "YES\n" : "NO\n");
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:17:28: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   17 |     for (unsigned s = 0; s < 1 << m; s++)
      |                          ~~^~~~~~~~

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