Submission #318475

#TimeUsernameProblemLanguageResultExecution timeMemory
318475GurbanBank (IZhO14_bank)C++17
100 / 100
175 ms1508 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...