제출 #1342236

#제출 시각아이디문제언어결과실행 시간메모리
1342236aaaaaaaa은행 (IZhO14_bank)C++20
100 / 100
192 ms179196 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ll long long

const int mxN = 1048576;

ll need[20],curr[20];
vector<ll> money[mxN];
ll dp[20][mxN];

bool f(ll i,ll mask){
	if(i<0) return 1;
	if(money[need[i]].size()==0) return 0;
	if(dp[i][mask]!=-1) return dp[i][mask];
	bool ok=0;
	for(auto it:money[need[i]]){
		if(!(mask & it)) ok |= f(i - 1, mask | it);
		if(ok) break;
	}
	return dp[i][mask]=ok;
}

void solve(ll tc) {
  ll n,m;cin>>n>>m;
  memset(dp,-1,sizeof(dp));

  for(ll i=0;i<n;++i) cin>>need[i];
  for(ll i=0;i<m;++i) cin>>curr[i];
  
  for(ll mask=0;mask<=(1ll<<m);++mask){
  	ll tot=0;
  	for(ll i=0;i<m;++i){
  		if(mask&(1ll<<i)) tot+=curr[i];
  	}
  	money[tot].pb(mask);
  }
  if(f(n-1,0)) yes;
  else no;

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve(0);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...