Submission #517311

#	Time	Username	Problem	Language	Result	Execution time	Memory
517311		zhangjishen	Bank (IZhO14_bank)	C++98	100 / 100	269 ms	4436 KiB

bank

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
const int MAXN = 21, MAXS = 11e5;

int n, m, a[MAXN], b[MAXN], s[MAXN], f[MAXS];

int sum(int i){
	int ans = 0;
	for(int j = 1; j <= m; j++)
		if(i & (1 << (j - 1)))
			ans += b[j];
	return ans;
}

int main(){
	// input
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
	}
	for(int i = 1; i <= m; i++)
		scanf("%d", &b[i]);
	// dp
	f[0] = 1;
	for(int i = 1; i < (1 << m); i++){
		int tot = sum(i), k = lower_bound(s + 1, s + 1 + n, tot) - s - 1, d = tot - s[k];
		if(tot > s[n]) continue;
		for(int j = 1; j <= m; j++)
			if((i & (1 << (j - 1))) && b[j] <= d)
				f[i] |= f[i ^ (1 << (j - 1))];
	}
	int ans = 0;
	for(int i = 0; i < (1 << m); i++)
		if(sum(i) == s[n])
			ans |= f[i];
	if(ans)
		printf("YES\n");
	else printf("NO\n");
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
bank.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", &b[i]);
      |   ~~~~~^~~~~~~~~~~~~

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