Submission #1293945

#TimeUsernameProblemLanguageResultExecution timeMemory
1293945loiloiloiBank (IZhO14_bank)C++20
100 / 100
366 ms10208 KiB
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
	return uniform_int_distribution<long long>(l, r)(rd);
}
int n, m;
vi a, b;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifdef LOCAL
		// freopen("TEST.inp", "r", stdin);
		// freopen("TEST.out", "w", stdout);
	#else
		// freopen("TEST.inp", "r", stdin);
		// freopen("TEST.out", "w", stdout);
	#endif
	
	cin >> n >> m;
	a.resize(n); b.resize(m);
	for (int& u : a) cin >> u;
	for (int& u : b) cin >> u;
	
	vi stat, s(1 << m);
	for (int i = 0; i < (1 << m); ++i) {
		for (int j = 0; j < m; ++j) {
			if (i >> j & 1) s[i] += b[j];
		}
	}
	stat.push_back(0);
	int suma = 0;
	for (int i = 0; i < n; i++) {
		suma += a[i];
		vi d(1 << m);
		for (int& mask : stat) {
			d[mask] = 1;
		}
		for (int j = 0; j < m; ++j) {
			for (int mask = (1 << m) - 1; mask >= 0; --mask) {
				if (mask >> j & 1) 
					d[mask] |= d[mask ^ (1 << j)];
			}
		}
		stat.clear();
		for (int mask = 0; mask < (1 << m); ++mask) {
			if (s[mask] == suma && d[mask]) stat.push_back(mask);
		}
	}
	cout << (stat.empty()? "NO" : "YES") << '\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...