Submission #565561

#	Time	Username	Problem	Language	Result	Execution time	Memory
565561		racsosabe	Bank (IZhO14_bank)	C++14	100 / 100	158 ms	10528 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];

void preprocess(){
	for(int i = 0; i < n; i++){
		nxt[a[i]] = a[i];
	}
	int last = MAX;
	for(int i = MAX - 1; i >= 0; i--){
		if(nxt[i] == i) last = i;
		nxt[i] = last;
	}
	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(new_sum == nxt[sum[mask] + 1]) 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:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:52:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  for(int i = 0; i < n; i++) scanf("%d", a + i);
      |                             ~~~~~^~~~~~~~~~~~~
bank.cpp:53:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  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