Submission #566659

#	Time	Username	Problem	Language	Result	Execution time	Memory
566659		racsosabe	Bank (IZhO14_bank)	C++14	100 / 100	603 ms	70088 KiB

bank

#include<bits/stdc++.h>
using namespace::std;

const int N = 20 + 5;
const int MASK = 1 << 20;

int n;
int m;
int neg;
int a[N];
int b[N];
int total;
int sum[MASK];
int memo[N][MASK];

void preprocess(){
	for(int mask = 1, l = 1 << m; mask < l; mask++) sum[mask] = sum[mask & (mask - 1)] + b[__builtin_ctz(mask)];
}

bool solve(){
	for(int pos = n - 1; pos >= 0; pos--){
		for(int mask = total; mask >= 0; mask--){
			if(__builtin_popcount(mask) < pos) continue;
			int &ans = memo[pos][mask];
			for(int m = mask ^ total; m > 0; m &= m - 1){
				int to = __builtin_ctz(m);
				int p = m & (-m);
				int new_mask = mask | p;
				if(sum[new_mask] == a[pos]) ans = max(ans, 1 + memo[pos + 1][new_mask]);
				else ans = max(ans, memo[pos][new_mask]);
			}
		}
	}
	return memo[0][0] == n;
}

int main(){
	scanf("%d %d", &n, &m);
	total = (1 << m) - 1;
	for(int i = 0; i < n; i++) scanf("%d", a + i);
	for(int i = 0; i < m; i++) scanf("%d", b + i);
	sort(a, a + n);
	for(int i = 1; i < n; i++) a[i] += a[i - 1];
	preprocess();
	puts(solve() ? "YES" : "NO");
	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool solve()':
bank.cpp:26:9: warning: unused variable 'to' [-Wunused-variable]
   26 |     int to = __builtin_ctz(m);
      |         ^~
bank.cpp: In function 'int main()':
bank.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:40:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  for(int i = 0; i < n; i++) scanf("%d", a + i);
      |                             ~~~~~^~~~~~~~~~~~~
bank.cpp:41:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  for(int i = 0; i < m; i++) scanf("%d", b + i);
      |                             ~~~~~^~~~~~~~~~~~~

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