Submission #712561

#	Time	Username	Problem	Language	Result	Execution time	Memory
712561		nishantc1527	Bank (IZhO14_bank)	C++14	71 / 100	1064 ms	6904 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef debug
#include "debug.h"
#endif
 
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
const int mod = (int) 1e9 + 7;
const int inf = 1061109567;
const ll infll = 4557430888798830399;

const int MAX_N = 20;

int n, m;
int a[MAX_N];
int b[MAX_N];
int dp[MAX_N][1 << MAX_N];
int sum[1 << MAX_N];

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 mask = 0; mask < 1 << m; mask ++) {
    int curr = 0;
    for(int i = 0; i < m; i ++) if((mask >> i) & 1) curr += b[i];
    sum[mask] = curr;
  }
  if(n == 1) {
    int ans = 0;
    for(int mask = 0; mask < 1 << m; mask ++) if(sum[mask] == a[0]) ans = 1;
    if(ans) cout << "YES\n";
    else cout << "NO\n";
    return;
  }
  for(int i = 0; i < n; i ++) {
    for(int mask = 0; mask < 1 << m; mask ++) {
      for(int sub = mask; sub; sub = (sub - 1) & mask) {
        if(sum[sub] == a[i]) {
          if(i == 0) dp[i][mask] = 1;
          else dp[i][mask] |= dp[i - 1][mask ^ sub];
        }
      }
    }
  }
  int ans = 0;
  for(int mask = 0; mask < 1 << m; mask ++) ans |= dp[n - 1][mask];
  if(ans) cout << "YES\n";
  else cout << "NO\n";
}

int main() {
#ifndef debug
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
#endif

  ios::sync_with_stdio(0);
  cin.tie(0);

  int t = 1;
  // cin >> t;
#ifdef debug
  int i = 1;
  t = 1e5;
#endif
 
  while(t --) {
#ifdef debug
    cout << "Case #" << i ++ << ": ";
#endif
    solve();
    cout << flush;
  }
}

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