Submission #752634

#	Time	Username	Problem	Language	Result	Execution time	Memory
752634		benjaminkleyn	Bank (IZhO14_bank)	C++17	100 / 100	117 ms	8624 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair

int n, m, a[20], b[20];
pair<int, int> dp[1 << 20];

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 (int mask = 1; mask < (1 << m); mask++)
    {
        for (int i = 0; i < m; i++)
        {
            auto [nxt, aux] = dp[mask ^ (1 << i)];
            if (mask & (1 << i))
                dp[mask] = max(dp[mask], mp(nxt + (aux + b[i] == a[nxt]), (aux + b[i]) * (aux + b[i] != a[nxt])));
        }
        if (dp[mask].first == n)
            return cout << "YES\n", 0;
    }
    cout << "NO\n";
    return 0;
}

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