Submission #91060

#	Time	Username	Problem	Language	Result	Execution time	Memory
91060		YottaByte	Bank (IZhO14_bank)	C++14	71 / 100	1070 ms	3140 KiB

bank

#include <iostream>
using namespace std;

const int N = 20 + 1;

#define ll long long
#define ok puts("OK");
int n, m, a[N], mx, cc;
int b[N], d[20001], dp[1 << 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)
{
	//cout << tr( mask, 2 ) << " " << c << endl;
	//cout << tr( p, 2 ) << " " << c << endl;
	//system("pause");
	
	cc = max(cc, c);
	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 ));
				
				int sum = 0;
				for(int i = 0; i < m; i++)
					if( tomask & ( 1 << i ))
						sum += b[i];
				
				if(sum < a[c])
				{
					//puts("Try");
					calc( tomask, p, c, i);
				}
				
				else if(sum == a[c])
				{
					//puts("Gotcha");
					dp[tomask] = c + 1;
					calc( 0, tomask | p, c + 1, 0);
				}
			}
		}
	}
}

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]), mx += b[i];
	
	d[0] = 1;
	for(int i = 0; i < m; i++)
		for(int j = mx; j >= b[i]; j--)
			if(d[j - b[i]])
				d[j] = 1;
	
	for(int i = 0; i < n; i++)
	{
		if(a[i] == 0)
		{
			puts("NO");
			return 0;
		}
	}
	
	calc(0);
	//cout << cc << endl;
	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
**/

Compilation message (stderr)

bank.cpp: In function 'std::__cxx11::string tr(int, int)':
bank.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(res.size() < m)
        ~~~~~~~~~~~^~~
bank.cpp: At global scope:
bank.cpp:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
bank.cpp: In function 'int main()':
bank.cpp:70: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
bank.cpp:75:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &b[i]), mx += b[i];
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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