Submission #1174311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174311		shoeib	Bank (IZhO14_bank)	C++20	100 / 100	422 ms	179528 KiB

bank

// Author: Muhammed Khaled Shoeib

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
//....................................................
// struct to speed-up the unordered data structures like map/set.
struct hash_function // unordered + modified hash >> ordered
{   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, typename Compare = less < T > > // O(logn)
using ordered_set = tree < T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
// less_equal:    asc.  not_unique, st.order_of_key(k) --> no. of items < k,  less: unique
// greater_equal: desc. not_unique, st.order_of_key(k) --> no. of items > k,  greater: unique
// *st.find_by_order(k) --> st[k] (Zero-indexed)
// less_equal (u can't erase here!) == multi-set
template < typename T > using maxpq = priority_queue < T >;
template < typename T > using minpq = priority_queue < T, vector< T >, greater< T > >;
//....................................................
#define     boost                  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define     precision(a)           cout << fixed << setprecision(a)
#define     alo                    cout << "alooooooooooo!" << endl
#define     YES                    cout << "YES" << endl
#define     Yes                    cout << "Yes" << endl
#define     yes                    cout << "yes" << endl
#define     NO                     cout << "NO" << endl
#define     No                     cout << "No" << endl
#define     no                     cout << "no" << endl
#define     ne                     cout << -1 << endl
#define     endl                   "\n"
#define     mem(mat, val)          memset(mat, val, sizeof(mat))
#define     ones(x)               __builtin_popcountll(x)
#define     msb(x)                63ll - __builtin_clzll(x)
#define     lsb(x)                __builtin_ffsll(x) - 1ll
//....................................................
#define     all(x)                 x.begin(), x.end()
#define     rall(x)                x.rbegin(),x.rend()
#define ceil_(a, b) (((ll)(a) + (ll)(b - 1)) / (ll)(b)) // up
#define floor_(a, b) (a / b) // down
#define round_(a, b) ((a + (b / 2ll)) / b) // nearest
//....................................................
// using ll  = int;                                                                     // take care of this shit!
using ll  = long long;
using i64 = long long; using i32 = int;
using ld  = long double;  using ull = unsigned long long;  using lli = long long int;
using cld = complex < long double >; using cd = complex < double >;
//......................................................
ll gcd_(ll x, ll y) { return y ? gcd_(y, x % y) : x; } // O(log(min(x, y)))
ll lcm_(ll a, ll b) { ll g = gcd_(a, b); return (a * b) / g; }
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define getrand(l, r) uniform_int_distribution<long long>(l, r)(rng)
//......................................................
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dx_diag[4] = { 1, 1, -1, -1 }, dy_diag[4] = { 1, -1, -1, 1 };
int dx_all[8] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy_all[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dx_knight[8] = {2, 2, 1, 1, -2, -2, -1, -1}, dy_knight[8] = {1, -1, 2, -2, 1, -1, 2, -2};
const ld  pi  = acos(-1); // 3.141592653589793238462643383279
const ld eps = 1e-9;
const ll inf = (ll)INT32_MAX; // 2e9
const ll oo = (ll)1e15;       // 1e15 (may cause OF in DP, Binary Search, ...)
const ll OO = (ll)INT64_MAX;  // 9e18
const ll mod  = (ll)1e9 + 7; // 1e9 + 7, 998244353
//..................................................... // string(len, char);
/*
 * think twice, code once.
 * think of different approaches to tackle a problem, write them down.
 * think of different views of the problem, don't look from only one side.
 * don't get stuck in one approach/problem.
 * common mistakes: line 48, overflow (sum of many numbers), corner cases, over/under count, infinite loops,
 * TLE, MLE (int instead of ll, using memset, Recursive DP, ...), RTE (out of bounds indexing), ....
 */
///____________________________________________ Shoeib __________________________________________________________


ll n, m;
vector < ll > a, b;

map < ll, vector < ll > > mp;
ll dp[20][(1ll << 20)];
ll slv(ll l, ll mask)
{
    if(l == n) return 1;


    ll &ret = dp[l][mask];
    if(ret != -1) return ret;
    ret = 0;


    for(const auto &i : mp[a[l]])
    {
        if(!(mask & i))
        {
            ret |= slv(l + 1, mask | i);
        }
    }




    return ret;
}

void solve()
{

    cin >> n >> m;
    a.resize(n); b.resize(m);
    for(auto &i : a) cin >> i;
    for(auto &i : b) cin >> i;

    mp.clear();
    for(ll mask = 0; mask < (1ll << m); mask++)
    {
        ll sm = 0;
        for(ll i = 0; i < m; i++)
        {
            if((mask >> i) & 1ll)
            {
                sm += b[i];
            }
        }
        mp[sm].push_back(mask);
    }

    mem(dp, -1);
    if(slv(0, 0)) YES;
    else NO;






    return;
}




signed main()
{
    boost;

    // freopen("bank.in", "r", stdin);
    // freopen("bank.out", "w", stdout);

    // precision(16);

    i32 _ = 1; //cin >> _;
    // cout.flush();
    while(_--) solve();
    return 0;
}

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