Submission #566669

#	Time	Username	Problem	Language	Result	Execution time	Memory
566669		racsosabe	Bank (IZhO14_bank)	C++14	71 / 100	1004 ms	25160 KiB

bank

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

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

int n;
int m;
int a[N];
int b[N];
int sum[MASK];
bool vis[N][MASK];
bool memo[N][MASK];

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

bool DP(int pos, int mask){
	if(pos == n) return true;
	if(vis[pos][mask]) return memo[pos][mask];
	bool ans = false;
	for(int m = mask; m > 0; m = mask & (m - 1)){
		if(sum[m] == a[pos] and DP(pos + 1, mask ^ m)){
			ans = true;
			break;
		}
	}
	vis[pos][mask] = true;
	return memo[pos][mask] = ans;
}

int 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);
	sort(a, a + n);
	preprocess();
	puts(DP(0, (1 << m) - 1) ? "YES" : "NO");
	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:37:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  for(int i = 0; i < n; i++) scanf("%d", a + i);
      |                             ~~~~~^~~~~~~~~~~~~
bank.cpp:38:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  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: 0 / 29