Submission #866339

#	Time	Username	Problem	Language	Result	Execution time	Memory
866339		hhaidang	Bank (IZhO14_bank)	C++14	19 / 100	139 ms	103044 KiB

bank

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define filein "r",stdin
#define fileout "w",stdout
#define pb push_back
#define FOR(i,j,k) for(ll i=j;i<=k;i++)
#define FORR(i,j,k) for (ll i=j;i>=k;i--)
using namespace std;
const ll maxn=1e7+5;
const ll mod=1e9+7;
ll n,k,m,b[maxn],res,ans,a[maxn],prefix[maxn],Left[maxn],f[maxn],consider[maxn];

bool bit(int mask,int i)
{
	return ( (mask>>i) & 1 > 0) ; 
}


void solve() {
	cin >> n >> m ;
	FOR(i,0,n-1) cin >> a[i] ;
	FOR(i,0,m-1) cin >> b[i] ;
	prefix[0] = a[0] ;
	for (int i=1; i<=m-1; i++) prefix[i] = prefix[i-1] + b[i] ;
	for (int mask=1; mask<(1LL<<m); mask++) {
		int sum = 0 ;
		for (int i=0; i<m; i++) if (bit(mask,i)) sum+=a[i];
		consider[mask] = upper_bound(prefix,prefix+m,sum) - prefix ;
		//left[mask] = sum ;
	}

	memset(f,-1,sizeof(f)) ;
	f[0] = 0 ;

	for (int mask=0; mask<(1LL<<m); mask++) {
		if (f[mask]==-1) continue ;
		int  cur_people = consider[mask] ;
		int  sum_left = Left[mask] ;
		for (int i=0; i<m; i++) if (bit(mask,i)==false) {
				int new_amt = sum_left + b[i] ;
				if (new_amt < a[cur_people] ) {
					f[mask|(1LL<<i)] = f[mask] ;
					Left[mask|(1LL<<i)] = new_amt ;
				} else if (new_amt == a[cur_people]) {
					f[mask|(1LL<<i)] = f[mask] + 1 ;
					Left[mask|(1LL<<i)] = 0 ;
				}
			}
			
	if (f[mask]==n) {
		cout<<"YES"<<endl;
		return ;
	}
			
	}
cout<<"NO"<<endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1 ;
	FOR(i,1,t) solve();
}

Compilation message (stderr)

bank.cpp: In function 'bool bit(int, int)':
bank.cpp:17:25: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   17 |  return ( (mask>>i) & 1 > 0) ;
      |                       ~~^~~

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