Submission #1293072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293072		fateless	Bank (IZhO14_bank)	C++20	100 / 100	328 ms	31660 KiB

bank

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define speedup cin.tie(0)->sync_with_stdio(0)
#define bitcount(x) __builtin_popcountll(x)
#define lla(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define Tp template<class T>
#define pb push_back
#define arr array

Tp using vc = vector<T>;
using pii = pair<int,int>;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;

#define int ll
const int inf = 1e18;
inline void solve(){
    int n, m;
    cin >> n >> m;
    vc<int> a(n), b(m); 
    for(int&x : a) cin >> x;
    for(int&x : b) cin >> x;
    map<int, vc<int>> memo;
    for(int mask = 0; mask < (1 << m); mask++) {
        int sum = 0;
        for(int i = 0; i < m; i++)
            if(mask >> i & 1) sum += b[i];

        memo[sum].pb(mask);
    }

    vc<int> dp(1 << m, 0); dp[0] = 1;
    for(int i = 0; i < n; i++) {
        vc<int> pre (1 << m); swap(pre, dp);
        for(int mask = 0; mask < (1 << m); mask++) if(pre[mask]){
            if(memo[a[i]].empty()) return cout << "NO\n", void();
            for(auto&sub : memo[a[i]])
                if((mask & sub) == 0)
                    dp[mask | sub] = 1;
            
        }
    } 
    int ans = count(all(dp), 1);
    if(ans > 0) cout << "YES\n";
    else cout << "NO\n";
}

signed main(){
    speedup;
    int t = 1;
    while(t--) solve();
}

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