Submission #873784

#	Time	Username	Problem	Language	Result	Execution time	Memory
873784		Irate	Bank (IZhO14_bank)	C++14	100 / 100	452 ms	94544 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>a, b;
vector<int>sums; /// sums[i] -> sum of elements in the set i
vector<vector<int>>lookup;
int dp[20][(1 << 20)];
bool rec(int indx, int mask){
	bool res = 0;
	if(indx == n)return 1;
	if(dp[indx][mask] != -1)return dp[indx][mask];
	for(int &i : lookup[a[indx]]){
		if((mask & i) == i){
			res |= rec(indx + 1, mask ^ i);
		}
	}
	return dp[indx][mask] = res;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	sums.resize((1 << m));
	lookup.resize(2e4 + 3);
	for(int i = 0;i < n;++i){
		cin >> a[i];
	}
	for(int i = 0;i < m;++i){
		cin >> b[i];
	}
	for(int i = 0;i < (1 << m);++i){
		int sum = 0;
		for(int j = 0;j < m;++j){
			if((i & (1 << j))){
				sum += b[j];
			}
		}
		sums[i] = sum;
		lookup[sum].push_back(i);
	}
	for(int i = 0;i < 20;++i){
		for(int j = 0;j < (1 << 20);++j){
			dp[i][j] = -1;
		}
	}

	if(rec(0, (1 << m) - 1)){
		cout << "YES";
	}
	else{
		cout << "NO";
	}
}	

Compilation message (stderr)

bank.cpp: In function 'bool rec(int, int)':
bank.cpp:17:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   17 |  return dp[indx][mask] = res;
      |         ~~~~~~~~~~~~~~~^~~~~

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