Submission #375646

#TimeUsernameProblemLanguageResultExecution timeMemory
375646gupta_samarthBank (IZhO14_bank)C++14
100 / 100
857 ms21228 KiB
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
	x += y;
	if( x >= m )
		x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
	x -= y;
	if( x < 0 )
		x += m;
}

vector<int> possible[LOGN];
bool dp[LOGN][1<<LOGN];

int main() 
{
	#ifdef gupta_samarth
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	fastio();

	int n,m;
	cin>>n>>m;
	vector<int>salary(n), notes(m);
	for(int i=0;i<n;i++) cin>>salary[i];
	for(int i=0;i<m;i++) cin>>notes[i];

	for(int i=1;i<(1<<m);i++)
	{
		int sum = 0;
		for(int j=0;j<m;j++)
			sum += ( (i>>j)&1 ? notes[j] : 0 );
		for(int j=0;j<n;j++)
		{
			if( sum == salary[j] )
			{
				possible[j].pb(i);
				// cout<<"possible: sum:"<<sum<<" person:"<<j+1<<" salary:"<<salary[j]<<" note_mask:"<<i,nl;
			}
		}
	}

	dp[0][0] = true;
	// dp[i][j] = satisfied first i people, using mask j notes
	for(int i=0;i<n;i++)
	{
		for(int submask: possible[i])
		{

			int comp_sub = ((1<<m)-1)^submask;
			for(int comp_mask=comp_sub;;comp_mask=(comp_mask-1)&comp_sub)
			{
				int mask = ((1<<m)-1)^comp_mask;
				dp[i+1][mask] |= dp[i][mask^submask];
				if( comp_mask == 0 ) break;
			}
		}
	}

	for(int mask=0;mask<(1<<m);mask++)
	{
		if( dp[n][mask] )
		{
			cout<<"YES";
			return 0;
		}
	}
	cout<<"NO",nl;


	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	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...