Submission #566661

#	Time	Username	Problem	Language	Result	Execution time	Memory
566661		racsosabe	Bank (IZhO14_bank)	C++14	100 / 100	267 ms	10444 KiB

bank

#include<bits/stdc++.h>
using namespace::std;
 
const int N = 20 + 5;
const int MAX = 1000 * 20 + 5;
const int MASK = 1 << 20;
 
int n;
int m;
int a[N];
int b[N];
int nxt[MAX];
int sum[MASK];
int memo[MASK];
bool vis[MASK];
set<int> used;
 
void preprocess(){
	for(int i = 0; i < n; i++) used.emplace(a[i]);
	for(int mask = 1; mask < 1 << m; mask++){
		sum[mask] = sum[mask & (mask - 1)] + b[__builtin_ctz(mask)];
	}
}
 
bool solve(){
	queue<int> Q;
	Q.emplace(0);
	while(!Q.empty()){
		int mask = Q.front(); Q.pop();
		for(int i = 0, p = 1; i < m; i++, p <<= 1){
			if(mask & p) continue;
			int new_sum = sum[mask] + b[i];
			if(used.count(new_sum)) memo[mask | p] = max(memo[mask | p], 1 + memo[mask]);
			else memo[mask | p] = max(memo[mask | p], memo[mask]);
			if(not vis[mask | p]){
				vis[mask | p] = true;
				Q.emplace(mask | p);
			}
		}
	}
	return *max_element(memo, memo + (1 << m)) == n;
}
 
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);
	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 'int main()':
bank.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  for(int i = 0; i < n; i++) scanf("%d", a + i);
      |                             ~~~~~^~~~~~~~~~~~~
bank.cpp:47:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  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