Submission #90784

#	Time	Username	Problem	Language	Result	Execution time	Memory
90784		daniel_02	Bank (IZhO14_bank)	C++17	100 / 100	374 ms	33320 KiB

bank

#include <bits/stdc++.h>

#define fr first
#define pb push_back
#define sc second
#define ll long long

using namespace std;

const int N = 23;

int a[N], b[N];
bool dp[N][(1 << 20) + 7];
vector<int>vec[(1 << 20) + 7];
bool us[(1 << 20) + 7];
vector<int>masks;

main()
{
	int n, m, x;
	
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &b[i]);
	}
	for (int mask = 1; mask < (1 << m); mask++)
	{
		int sm = 0;
		for (int i = 0; i < m; i++)
		{	
			if (mask & (1 << i))
				sm += b[i];
		}
		vec[sm].pb(mask);
	}
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		masks.clear();
		for (int j = 0; j < vec[sum].size(); j++)
		{
			int mask = vec[sum][j];
			if (i == 0 || us[mask])masks.pb(mask);
		}
		if (masks.size() == 0)
		{
			puts("NO");
			return 0;
		}
		memset(us, 0, sizeof(us));
		for (int j = 0; j < masks.size(); j++)
		{
			int mask = masks[j];
			us[mask] = 1;
		}
		for (int mask = 1; mask < (1 << m); mask++)
		{
			if (us[mask])
			{
				for (int j = 0; j < m; j++)
				{
					us[mask | (1 << j)] = 1;
				}
			}
		}
	}
	puts("YES");
}
/*
4 20
5 5 5 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/

Compilation message (stderr)

bank.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
bank.cpp: In function 'int main()':
bank.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec[sum].size(); j++)
                   ~~^~~~~~~~~~~~~~~~~
bank.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < masks.size(); j++)
                   ~~^~~~~~~~~~~~~~
bank.cpp:20:12: warning: unused variable 'x' [-Wunused-variable]
  int n, m, x;
            ^
bank.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
bank.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]);
   ~~~~~^~~~~~~~~~~~~

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