제출 #17969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17969		Adilkhan	은행 (IZhO14_bank)	C++98	100 / 100	228 ms	26496 KiB

bank

#include <bits/stdc++.h>

#define pb push_back
#define endl "\n"
#define mp make_pair 
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define fname ""
#define sz(x) (int)(x.size())

typedef long long ll;

using namespace std;

const ll N = (ll)(5e5) + 322;
const ll INF = (ll)(1e9);
const ll mod = (ll)(1e9) + 7;
const double eps = 1e-9;

int n, m, sum;

vector <int> v[N], a, b;

bool u[21][(1 << 20) + 322];

void calc(int x, int pmsk) {
	if (x == n) {
		cout << "YES"; exit(0); 
	}	
	if (u[x][pmsk]) return;
	u[x][pmsk] = 1;
	for (auto it : v[x]) {
		if (it & pmsk) continue;
		calc(x + 1, pmsk ^ it);
	}
}

int main () {
	ios_base :: sync_with_stdio (false); cin.tie(0);
//	freopen(fname".in", "r", stdin);
	//freopen(fname".out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {int x; cin >> x; a.pb(x);}
	for (int i = 1; i <= m; ++i) {int x; cin >> x; b.pb(x);}
	for (int mask = 0; mask < (1 << m); ++mask) {
		sum = 0;
		for (int i = 0; i < m; ++i) {
			if ((1 << i) & mask) {
				sum += b[i];			
			}
		}		
		for (int i = 0; i < n; ++i) {
			if (sum == a[i]) {
				v[i].pb(mask);			
			}
		}
	}
	calc(0, 0);
	cout << "NO";
	return 0;
}

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