Submission #375634

#	Time	Username	Problem	Language	Result	Execution time	Memory
375634		gupta_samarth	Bank (IZhO14_bank)	C++14	52 / 100	1080 ms	884 KiB

bank

#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;
}

bool possible[LOGN][1<<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][i] = true;
				// 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 mask=0;mask<(1<<m);mask++)
		{
			for(int submask=mask;;submask=(submask-1)&mask)
			{
				dp[i+1][mask] |= ( possible[i][submask] && dp[i][mask^submask] );
				if( submask == 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;
}

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