Submission #488456

#TimeUsernameProblemLanguageResultExecution timeMemory
488456saransh2708Bank (IZhO14_bank)C++14
100 / 100
152 ms16712 KiB
//....SARANSH GUPTA....\  

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fo(p, n) for (int i = p; i < n; i++)
#define FIO                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define endl "\n"
#define pb push_back
#define mod 1000000007
#define all(a) a.begin(), a.end()

const int N = 21, INF = 1e12;
int n, x, y, z, ans, k, q, m;

int a[N], b[N];

signed main()
{
    cin >> n;
    cin >> m;
    fo(0, n) cin >> a[i];
    fo(0, m) cin >> b[i];
    sort(a, a + n);
    sort(b, b + m);
    array<int, 2> dp[(1LL << m) + 2];
    fo(0, 1LL << m)
        dp[i] = {0, 0};
    for (int mask = 0; mask < (1LL << m) - 1; mask++)
    {
        int current = dp[mask][0];
        int curr_val = dp[mask][1];
        fo(0, m)
        {
            int val = 1LL << i;
            if (val & mask)
            {
                continue;
            }
            if (current == n)
            {
                dp[mask | val] = {n, 0};
            }
            else
            {
                if (curr_val + b[i] == a[current])
                {
                    dp[mask | val] = max(dp[mask | val], {current + 1, 0});
                }
                else if (curr_val + b[i] < a[current])
                {
                    dp[mask | val] = max(dp[mask | val], {current, curr_val + b[i]});
                }
                else
                {
                    dp[mask | val] = max(dp[mask | val], dp[mask]);
                }
            }
        }
    }
    if (dp[(1LL << m) - 1][0] == n)
        cout << "YES\n";
    else
        cout << "NO\n";
}

Compilation message (stderr)

bank.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //....SARANSH GUPTA....\
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...