제출 #1293945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293945		loiloiloi	은행 (IZhO14_bank)	C++20	100 / 100	366 ms	10208 KiB

bank

#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;
}

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