Submission #1001427

#TimeUsernameProblemLanguageResultExecution timeMemory
1001427vjudge1Bank (IZhO14_bank)C++17
0 / 100
1 ms2396 KiB
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define x first
#define y second
#define bit(i,j) ((j >> i) & 1)
using namespace std;

const long long inf = 1e9+1;
const int mod = 1e9+7;
const int MAXN = 2e5+100;

bool dp[25][(1<<20)+2]; 
int cnt[(1 << 20)+2];
int32_t main(){
  	//freopen("A.inp", "r", stdin);
	//freopen("A.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n , m; cin >> n >> m;
	vector<int> pre(n+1) , a(n+1) , b(m+1);
	for(int i = 1; i <= n ; i ++) cin >> a[i] , pre[i] = pre[i-1] + a[i];
	for(int i = 1; i <= m ; i ++) cin >> b[i];
	
	for(int msk = 1 ; msk < (1 << m) ; msk++){
		for(int i = 0 ; i < m ; i++) if(bit(i , msk)) cnt[msk] += b[i+1];
	}
	dp[0][0] = 1;
	for(int i = 1 ; i <= n ; i++){
		for(int msk = 1 ; msk < (1 << m) ; msk++){
			if(cnt[msk] != pre[i]) continue;
			for(int s = msk ; s > 0 ; s = (s-1) & msk){
				if(cnt[msk^s] == a[i] && dp[i-1][s]) {dp[i][msk] = 1; break;}
			}
		}
	}
	for(int msk = 1 ; msk < (1 << m) ; msk++){
		if(dp[n][msk]){
			cout << "YES\n"; return 0;
		}
	}
	cout << "NO\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...