Submission #1089293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089293		pablo777	Bank (IZhO14_bank)	C++17	100 / 100	221 ms	24240 KiB

bank

/*
CODED BY : Super_KAZAKH(-:  >---->  Hazik of Yedige Ashirbek
 _____     _____         _______________                 ___        _______           ________________      _______________
/\    \   /\    \       /\              \               /\   \     /\      \         /                \    /\              \
\ \    \  \ \    \      \ \    __________\              \ \   \    \ \      \       /\     ____________\   \ \    __________\
 \ \    \  \ \    \      \ \   \_________/               \ \   \    \ \      \      \ \    \                \ \   \_________/
  \ \    \  \ \    \      \ \   \                         \ \   \    \ \      \      \ \    \                \ \   \
   \ \    \  \ \    \      \ \   \                         \ \   \    \ \      \      \ \    \                \ \   \
    \ \    \__\_\    \      \ \   \__________        _______\_\   \    \ \      \      \ \    \     ______     \ \   \__________
     \ \              \      \ \    _________\      /              \    \ \      \      \ \    \    \     \     \ \    _________\
      \ \____      ____\      \ \   \________/     /\    ________   \    \ \      \      \ \    \    \__   \     \ \   \________/
       \/___ \     \           \ \   \             \ \   \     \ \   \    \ \      \      \ \    \      \   \     \ \   \
            \ \     \           \ \   \             \ \   \     \ \   \    \ \      \      \ \    \      \   \     \ \   \
             \ \     \           \ \   \             \ \   \     \ \   \    \ \      \      \ \    \      \   \     \ \   \
              \ \     \           \ \   \___________  \ \   \     \ \   \    \ \      \      \ \    \_____/    \     \ \   \___________
               \ \     \           \ \              \  \ \   \_____\_\   \    \ \      \      \ \              /      \ \              \
                \ \_____\           \ \______________\  \ \_______________\    \ \______\      \ \____________/        \ \______________\
                 \/_____/            \/______________/   \/_______________/     \/______/       \/___________/          \/______________/
                                                                                                                                            */
// find_by_order(x)
// order_of_key(x)
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.end(), x.begin()
#define f first
#define s second
#define d(a) (a * (a + 1)) / 2
#define ent '\n'
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef double db;
typedef tree<int, null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
const ll inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 1e3 + 7;
const int INF = 1e9 + 2;
const int PP = 31;
const int MOD = 998244353;
void ALLAHU_AKBAR() {
	ios_base::sync_with_stdio (0);
	cin.tie (0);
//  freopen("sum.in","r",stdin);
//	freopen("sum.out","w",stdout);
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};
ll binpow (ll a, ll n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n - 1) * a;
	else {
		ll b = binpow (a, n / 2);
		return b * b;
	}
}
int n, m, a[25], b[25];
vector < int > dp[25];
vector < int > gg[25];
vector < int > c[N];
bool ok[21][2000000];
void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[a[i]].pb(i);
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    for (int i = 1; i < binpow(2, m); i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            if ((i >> j) % 2) sum += b[j + 1];
        }
        if (sum <= 1000) {
            for (int j : c[sum]) gg[j].pb(i);
        }
    }
    dp[0].pb(0);
    for (int i = 0; i < n; i++) {
        for (int j : dp[i]) {
            for (int x : gg[i + 1]) {
                if (!(j & x)) {
                    if (!ok[i + 1][j | x]) dp[i + 1].pb(j | x);
                    ok[i + 1][j | x] = true;
                    if (i + 1 == n) {
                        cout << "YES";
                        return;
                    }
                }
            }
        }
    }
    cout << "NO";
}
signed main() {
    ALLAHU_AKBAR();
    int IOI = 1;
// 	cin >> IOI;
	int g = 0;
	while (-- IOI + 1) {
		g++;
		solve();
	}
	return 0;
}

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