Submission #683107

#	Time	Username	Problem	Language	Result	Execution time	Memory
683107		brijeshSiwach	Bank (IZhO14_bank)	C++17	100 / 100	538 ms	180736 KiB

bank

//----------------------- JAI BABA KI -----------------------//    

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
 
#define all(x) x.begin(), x.end()
#define nl cout<<"\n"
#define ar  array
#define PRECISION 9
#define fast_IO ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define clock() cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

#ifdef LOCAL
#include "../Library/debug.h"
#else 
#define dbg(...) "OM BHOLE"
#endif


//----------------------- ये कर लो पहले -----------------------//
const int mxN=1<<21;
int n, m, a[mxN], b[mxN], dp[21][mxN];
unordered_map<int,vector<int>> maskp; 

int go(int pos, int mask){
    if(pos==n) return 1;
    if(dp[pos][mask]==-1){
        int ans=0;
        for(int smask: maskp[a[pos]]){
            if(mask&smask) continue;
            ans|=go(pos+1,mask|smask);
        }
        dp[pos][mask]=ans;
    }
    return dp[pos][mask];
}

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int i=0;i<1<<m;i++){
        int sum=0;
        for(int j=0;j<m;j++){
            if(i&(1<<j)) sum+=b[j];
        }
        maskp[sum].push_back(i);
    }
    memset(dp,-1,sizeof(dp));
    cout<<(go(0,0)==1?"YES":"NO");
}

//----------------------- पढाई कर ले -----------------------//

int main(){
    if (0) cout<<fixed<<setprecision(PRECISION);
    fast_IO;
    int T=1;
    // cin>>T;
    // freopen("bank.in", "r",stdin);
    // freopen("bank.out", "w",stdout);
    while(T--){
        solve();
        clock();
    }
    return 0;
}

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