Submission #1101860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101860		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	104 ms	16892 KiB

bank

#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define f first
#define s second
#define LSOne(s) ((s) & -(s))
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> iii;
int mod = 1e9 + 7;
const int mx9 = 1e9 + 1;
const int mx6 = 1e6 + 1;
const int maxn = 21;
const int maxc = 1002;
vector<pii> dp((1 << maxn), {0, 0});
vector<int> salaries(maxn), banknotes(maxn);
int n, m;
void solve()
{
    cin >> n >> m;
    bool ans = false;
    for (int x = 0; x < n; x++)
    {
        cin >> salaries[x];
    }
    for (int y = 0; y < m; y++)
    {
        cin >> banknotes[y];
    }
    for (int mask = 0; mask < (1 << m); mask++)
    {
        if (ans)
            break;
        for (int pos = 0; pos < m; pos++)
        {
            if ((mask & (1 << pos)) >= 1)
                continue;
            int idx = dp[mask].f;
            int currentval = dp[mask].s;
            // cout << currentval << " " << idx << " " << pos << " " << mask << "\n";
            if (idx < n)
            {
                if (currentval + banknotes[pos] == salaries[idx])
                {
                    idx++;
                    currentval = 0;
                    dp[mask | (1 << pos)] = max(dp[mask | (1 << pos)], make_pair(idx, currentval));
                    if (idx == n)
                    {
                        ans = true;
                        break;
                    }
                }
                else if(currentval + banknotes[pos] < salaries[idx])
                {
                    currentval += banknotes[pos];
                    dp[mask | (1 << pos)] = max(dp[mask | (1 << pos)], make_pair(idx, currentval));
                }
            }
        }
    }
    ans ? cout << "YES" : cout << "NO";
}
signed main()
{
    // freopen("movie.in", "r", stdin);
    // freopen("movie.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

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