oj.uz

Submission #771852

# Submission time Handle Problem Language Result Execution time Memory
771852 2023-07-03T10:34:12 Z manavjeet02 Bank (IZhO14_bank) C++14
71 / 100
 1000 ms 33108 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 72 ms 16708 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 74 ms 16724 KB Output is correct
9 Correct 72 ms 16724 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1344 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 1732 KB Output is correct
4 Correct 2 ms 2260 KB Output is correct
5 Correct 3 ms 1748 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 1472 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 2 ms 2236 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 72 ms 16708 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 74 ms 16724 KB Output is correct
9 Correct 72 ms 16724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 1344 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 3 ms 1732 KB Output is correct
23 Correct 2 ms 2260 KB Output is correct
24 Correct 3 ms 1748 KB Output is correct
25 Correct 2 ms 1108 KB Output is correct
26 Correct 2 ms 980 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 2 ms 1472 KB Output is correct
29 Correct 2 ms 1492 KB Output is correct
30 Correct 2 ms 2236 KB Output is correct
31 Correct 270 ms 24916 KB Output is correct
32 Execution timed out 1076 ms 33108 KB Time limit exceeded
33 Halted 0 ms 0 KB -