Submission #318475

#	Time	Username	Problem	Language	Result	Execution time	Memory
318475		Gurban	Bank (IZhO14_bank)	C++17	100 / 100	175 ms	1508 KiB

bank

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

using ll = long long;

int n,m,a[22],b[22],p[22];
int sum,pos;
bool dp[(1<<22)];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i],p[i]=p[i-1]+a[i];
	for(int i = 0;i < m;i++) cin >> b[i];

	dp[0] = 1;
	for(int i = 0;i < (1<<m);i++){
		sum = 0; for(int j = 0;j < m;j++) if((1<<j) & i) sum += b[j];
		int pos = lower_bound(p+1,p+n+1,sum) - p;
		if(pos == n+1) continue;
		for(int j = 0;j < m;j++) if((1<<j) & i and b[j] <= sum-p[pos-1]) dp[i] |= dp[i-(1<<j)];
		if(sum == p[n] and dp[i]) return cout<<"YES",0;
	}
	cout<<"NO";
}

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