Submission #91069

#	Time	Username	Problem	Language	Result	Execution time	Memory
91069		YottaByte	Bank (IZhO14_bank)	C++14	100 / 100	453 ms	3196 KiB

bank

#include <stdio.h>
#include <stdlib.h>
using namespace std;

const int N = 22;

int n, m, a[N], b[N];
int dp[1 << N], ui[N], uj[N];
/**
string tr(int a, int b)
{
	string res = "";
	while(a)
	{
		res += char(a % b + '0');
		a /= b;
	}
	while(res.size() < m)
	{
		res += '0';
	}
	return res;
}
**/
void calc(int mask, int p = 0, int c = 0, int last = 0, int sum = 0)
{
	//cout << tr( mask, 2 ) << " " << c << endl;
	//cout << tr( p, 2 ) << " " << c << endl;
	//system("pause");
	
	if(c == n)
	{
		puts("YES");
		exit(0);
	}
	
	for(int i = last; i < m; i++)
	{
		if(!( mask & ( 1 << i )))
		{
			if(!( p & ( 1 << i )))
			{
				int tomask = ( mask | ( 1 << i ));
				
				if(sum + b[i] < a[c])
				{
					//puts("Try");
					calc( tomask, p, c, i, sum + b[i]);
				}
				
				else if(sum + b[i] == a[c])
				{
					//puts("Gotcha");
					dp[tomask] = c + 1;
					sum += b[i];
					calc( 0, tomask | p, c + 1, 0, 0);
				}
				
				else
				{
					//puts("BigTry");
					calc( tomask, p, c, i, sum + b[i]);
				}
			}
		}
	}
}

main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	
	for(int i = 0; i < m; i++)
		scanf("%d", &b[i]);
	
	if(n < m)
		calc(0);
	else if(n == m)
	{
		int ans = 0;
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				if(uj[j] || ui[i])
					continue;
				
				if(a[i] == b[j])
				{
					ui[i] = 1;
					uj[j] = 1;
					ans ++;
				}
			}
		}
		if(ans == n)
			puts("YES");
		else puts("NO");
		return 0;
	}
	
	puts("NO");
}
/**
1 5
8
4 2 5 1 3

2 6
9 11
6 8 3 5 4 10

2 6
9 11
6 8 3 5 2 10

5 9
3 7 4 10 9
3 2 9 6 3 9 2 9 1


**/

Compilation message (stderr)

bank.cpp:69:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
bank.cpp: In function 'int main()':
bank.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
bank.cpp:76: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