Submission #566657

#	Time	Username	Problem	Language	Result	Execution time	Memory
566657		racsosabe	Bank (IZhO14_bank)	C++14	71 / 100	1035 ms	72188 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];
bool vis[N][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)];
}

int DP(int pos, int mask){
	if(pos == n) return 0;
	if(vis[pos][mask]) return memo[pos][mask];
	int ans = 0;
	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 + DP(pos + 1, new_mask));
		else ans = max(ans, DP(pos, new_mask));
	}
	vis[pos][mask] = true;
	return memo[pos][mask] = ans;
}

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