Submission #1217257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217257		amaninnight	Bank (IZhO14_bank)	C++20	52 / 100	1096 ms	16008 KiB

bank

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
#define F first
#define S second 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> VI;
typedef vector<ll> VLL;

const int maxn = 21;

int a[maxn], b[maxn];
int money[1<<maxn], dp[maxn][1<<maxn];
VI bag[1000 * maxn];

void MAIN(){
    int n, m;   cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++)  cin >> b[i];
    for(int mask = 1; mask < (1<<m); mask++){
        money[mask] = money[mask - (1<<(__builtin_ctz(mask)))] + b[__builtin_ctz(mask)];
        bag[money[mask]].pb(mask);
    }
    for(int mask = 0; mask < (1<<m); mask++)    dp[0][mask] = 1;
    for(int i = 1; i <= n; i++){
        for(int mask = 1; mask < (1<<m); mask++){
            for(int smask : bag[a[i]]){
                // cout << "SFSF " << endl;
                if((smask|mask) == mask){
                    dp[i][mask] |= dp[i-1][mask-smask];
                }
            }
        }
    }
    // for(int i = 0; i <= n; i++){
    //     for(int mask = 0; mask < (1<<m); mask++)    cout << i << " " << mask << " " << dp[i][mask] << endl;
    // }
    if(dp[n][(1<<m)-1]) cout << "YES" << endl;
    else    cout << "NO" << endl;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0), cout.tie(0);   
    
    int _ = 1;
    //cin >> _;
    while(_--)
        MAIN();
}

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