Submission #771852

#	Time	Username	Problem	Language	Result	Execution time	Memory
771852		manavjeet02	Bank (IZhO14_bank)	C++14	71 / 100	1076 ms	33108 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(a) a.begin(), a.end()
#define scnarr(a, n)            \
    for (int i = 0; i < n; ++i) \
    cin >> a[i]
#define vi vector<int>
#define pi pair<int, int>
#define vpi vector<pi>
#define _sort(a) sort(all(a))
#define __sort(a, x) sort(all(a), x)
#define loop(i, n) for (int i = 0; i < n; ++i)
#define vvi vector<vi>
const int MOD = 1e9 + 7;

class custom_hash
{
public:
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <typename T>
using max_heap = priority_queue<T>;

template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
using uset = unordered_set<T, custom_hash>;

template <typename T1, typename T2>
using umap = unordered_map<T1, T2, custom_hash>;

int add(int a, int b, int mod = MOD)
{
    return (a + b) % mod;
}

int sub(int a, int b, int mod = MOD)
{
    return (a - b + mod) % mod;
}

int mul(int a, int b, int mod = MOD)
{
    return ((a % mod) * (b % mod)) % mod;
}

bool recur(vi &salary, vi &money, int i, int mask, vvi &dp)
{
    if (i == salary.size())
        return true;

    if (dp[i][mask] != -1)
        return dp[i][mask];

    bool flag = false;
    int rem = (1 << money.size()) - 1 - mask;
    for (int sb = rem; sb > 0; sb = (sb - 1) & rem)
    {
        int val = 0;
        for (int x = 0; x < money.size(); x++)
        {
            if (sb & (1 << x))
                val += money[x];
        }
        if (val == salary[i])
            flag |= recur(salary, money, i + 1, mask + sb, dp);
    }
    return dp[i][mask] = flag;
}

void solve()
{
    int n, m;
    cin >> n >> m;

    vi arr(n);
    scnarr(arr, n);

    vi money(m);
    scnarr(money, m);

    vvi dp(n, vi((1 << m), -1));
    cout << (recur(arr, money, 0, 0, dp) ? "YES" : "NO") << endl;
}

int32_t main()
{
    // freopen("bank.in", "r", stdin);
    // freopen("bank.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
}

Compilation message (stderr)

bank.cpp: In function 'bool recur(std::vector<long long int>&, std::vector<long long int>&, long long int, long long int, std::vector<std::vector<long long int> >&)':
bank.cpp:64:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if (i == salary.size())
      |         ~~^~~~~~~~~~~~~~~~
bank.cpp:75:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int x = 0; x < money.size(); x++)
      |                         ~~^~~~~~~~~~~~~~
bank.cpp:83:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   83 |     return dp[i][mask] = flag;

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