Submission #843773

#	Time	Username	Problem	Language	Result	Execution time	Memory
843773		Firas_Briki	Bank (IZhO14_bank)	C++17	100 / 100	433 ms	213568 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #else
// #define dbg(...)
// #endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 2e4 + 7;
const int Nax = 15;
const int LOG = 18;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}

vector<int> s[N_Max];
int dp[25][(1 << 21)];
int a[25], b[25];
int N, M;

int work(int i, int mask){
    if (i >= N) return 1;
    int &ret = dp[i][mask];
    if (ret != -1) return ret;
    ret = 0;
    for (int curr : s[a[i]])
        if (!(mask & curr)) ret |= work(i + 1, mask | curr);
    return ret;
}

void solve(){
    cin >> N >> M;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < M; i++) cin >> b[i];
    for (int mask = 0; mask < (1 << M) ; mask++){
        int sum = 0;
        for (int i = 0; i < M; i++)
            if (mask & (1 << i)) sum += b[i];
        s[sum].pb(mask);
    }
    int ans = work(0, 0);
    if (ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main(){
    FAST
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}

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