제출 #1269452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269452		g4yuhg	은행 (IZhO14_bank)	C++20	71 / 100	1100 ms	86744 KiB

bank

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "subsequence"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll getbit(ll mask, ll i) {
	return (mask >> i) & 1;
}
ll onbit(ll mask, ll i) {
	return mask | (1 << i);
}

ll n, m;
ll a[30], b[30], id[30];
vector<ll> vt[30];

bool cmp(ll u, ll v) {
	return vt[u].size() < vt[v].size();
}

bool cmp2(ll u, ll v) {
	return __builtin_popcount(u) < __builtin_popcount(v);
}

ll f[21][(1 << 20)];

ll dp(ll i, ll mask) {
	if (i > n) {
		return 1;
	}
	if (f[i][mask] != -1) {
		return f[i][mask];
	}
	bool res = 0;
	for (auto it : vt[id[i]]) {
		if ((it & mask) == 0) {
			ll newmask = it | mask;
			if (dp(i + 1, newmask) == 1) {
				res = 1;
				break;
			}
		}
	}
	f[i][mask] = res;
	return res;
}

void sub1() {
	memset(f, -1, sizeof(f));
	for (int i = 1; i <= n; i ++) {
		for (int mask = 0; mask < (1 << m); mask ++) {
			ll sum = 0;
			for (int j = 1; j <= m; j ++) {
				if (getbit(mask, j - 1) == 0) continue;
				sum += b[j];
			}
			if (sum == a[i]) {
				vt[i].push_back(mask);
			}
		}
		sort(vt[i].begin(), vt[i].end(), cmp2);
	}
	for (int i = 1; i <= n; i ++){
		id[i] = i;
	}
	sort(id + 1, id + 1 + n, cmp);
	if (dp(1, 0) == 1) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}
}

bool klinh;

signed main(void) {
    faster;
	  
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i ++) {
		cin >> b[i];
	}
	sub1();
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

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