Submission #1269455

#TimeUsernameProblemLanguageResultExecution timeMemory
1269455g4yuhgBank (IZhO14_bank)C++20
71 / 100
1096 ms86740 KiB
//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)], pf[30];

ll cal(ll mask) {
	ll sum = 0;
	for (int j = 1; j <= m; j ++) {
		if (getbit(mask, j - 1) == 1) continue;
		sum += b[j];
	}
	return sum;
}

ll dp(ll i, ll mask) {
	if (i > n) {
		return 1;
	}
	if (f[i][mask] != -1) {
		return f[i][mask];
	}
	if (pf[n] - pf[i - 1] > cal(mask)) {
		f[i][mask] = 0;
		return 0;
	}
	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);
	for (int i = 1; i <= n; i ++) {
		pf[i] = pf[i - 1] + a[id[i]];
	}
	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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...