Submission #375690

#	Time	Username	Problem	Language	Result	Execution time	Memory
375690		gupta_samarth	Bank (IZhO14_bank)	C++14	100 / 100	794 ms	30784 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;
}

vector<int> possible[LOGN*1000];
bool dp[LOGN][1<<LOGN];
int sum[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];

	sum[0] = 0;
	for(int i=1;i<(1<<m);i++)
	{
		sum[i] = sum[i&(i-1)] + notes[__builtin_ctz(i)];
		possible[sum[i]].pb(i);
	}

	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[salary[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;
}

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