Submission #607623

#	Time	Username	Problem	Language	Result	Execution time	Memory
607623		sushant52	Bank (IZhO14_bank)	C++17	52 / 100	1097 ms	21744 KiB

bank

/////////////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////
#define MOD 1000000009
#define BIG 100000000000000000
#define PB push_back
#define MP make_pair
#define inn(x)   \
	long long x; \
	cin >> x;
#define all(x) (x).begin(), (x).end()
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define spp << " "
#define int long long
const int mod = 5;
int powmod(int a, int b)
{
	int res = 1;
	a %= mod;
	assert(b >= 0);
	for (; b; b >>= 1)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
	}
	return res;
}
// #define endl "\n"

// struct comparator
// {
// 	bool operator()(const pair<int,pair<int,int> > p1 , const pair<int,pair<int,int> > p2)
//  	{
// 		return (p1.first>p2.first || p1.second.first<p2.second.first);
// 	}
// };

// int not_prime[100001]={0};
// int arr[100001]={0};

// void seive()
// {
// 	not_prime[0]=not_prime[1]=1;
// 	for (int i = 2; i * i <= 100000; i++)
// 	{
//     	if(!not_prime[i])
//     	{
//        		for(int j = i * i; j <= 100000; j += i)
//          		not_prime[j] = 1;
//   		}
// 	}
// }

// void kprime()
// {
// 	arr[0]=0;arr[1]=0;arr[2]=1;arr[3]=1;
// 	for(int i=4;i<100001;++i)
// 	{
// 		int temp=i;
// 		for(auto x:prime)
// 		{
// 			if(x*x>temp)
// 				break;
// 			if(temp%x==0)
// 				++arr[i];
// 			while(temp%x==0)
// 				temp/=x;
// 		}
// 		if(temp>1)
// 			++arr[i];
// 	}
// }

int n, m;
vector<int> req;
vector<int> nums;
map<pair<int, int>, bool> dp;

bool recurse(int i, int cur, int mask)
{
	if (i >= req.size())
		return true;
	if (dp.find({cur, mask}) != dp.end())
		return dp[{cur, mask}];
	if (cur == 0)
		return dp[{cur, mask}] = recurse(i + 1, i + 1 < req.size() ? req[i + 1] : 0, mask);
	if (cur < 0)
		return false;

	bool flag = false;

	for (int j = 0; j < m; ++j)
	{
		if (mask & (1 << j))
			flag = flag || recurse(i, cur - nums[j], mask ^ (1 << j));
	}

	return (dp[{cur, mask}] = flag);
}

void solve()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		req.push_back(x);
	}

	for (int i = 0; i < m; ++i)
	{
		int x;
		cin >> x;
		nums.push_back(x);
	}

	cout << (recurse(0, req[0], (1 << m) - 1) ? "YES" : "NO");

	return;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// inn(t);
	// while (t--)
	solve();
}

Compilation message (stderr)

bank.cpp: In function 'bool recurse(long long int, long long int, long long int)':
bank.cpp:85:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  if (i >= req.size())
      |      ~~^~~~~~~~~~~~~
bank.cpp:90:49: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   return dp[{cur, mask}] = recurse(i + 1, i + 1 < req.size() ? req[i + 1] : 0, mask);
      |                                           ~~~~~~^~~~~~~~~~~~

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