Submission #645595

#	Time	Username	Problem	Language	Result	Execution time	Memory
645595		kith14	Bank (IZhO14_bank)	C++17	100 / 100	274 ms	94680 KiB

bank

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

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define x first
#define y second
#define mp make_pair
#define pb push_back

const ll N = 5e5+5, MOD = 1e9+7, M = 1048690;
ll tc = 1, n, m, ar[N], br[N], vs[21][M];
string s, s1, s2, ye = "YES", no = "NO";

vector<ll> vr[25];

void rec(ll idx, ll mask){
  if(idx > n){
    cout << ye << endl;
    exit(0);
  }
  if (vs[idx][mask]) return;
  vs[idx][mask] = 1;
  for (auto i : vr[idx]){
    if ((mask&i)) continue;
    rec(idx+1,mask+i);
  }
}

void input(){
  cin >> n >> m;
  repp(i,1,n) cin >> ar[i];
  repp(i,0,m-1) cin >> br[i];
}

void solve(){
  repz(bt,1,(1<<m)){
    ll sum = 0;
    repz(i,0,m){
      if ((1<<i)&bt) sum += br[i];
    }
    repp(i,1,n){
      if (sum == ar[i]) vr[i].pb(bt);
    }
  }
  rec(1,0);
  cout << no << endl;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

/*
It's youuuuu
Loving's so easy to dooo
*/

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