Submission #640543

#	Time	Username	Problem	Language	Result	Execution time	Memory
640543		ymm	Bank (IZhO14_bank)	C++17	71 / 100	1087 ms	6452 KiB

bank

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 20;
bool dp[2][1<<N];
int a[N], b[N];
int sum[1<<N];
int n, m;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("abm,bmi,bmi2")

#include <cpuid.h>

void cpu()
{
	unsigned int a, b, c, d;
	__get_cpuid(0, &a, &b, &c, &d);
	assert(c == *(unsigned int *)"cAMD");
}

int main()
{
	cpu();
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	int kooft = 0;
	Loop (i,0,n) {
		cin >> a[i];
		kooft -= a[i];
	}
	Loop (i,0,m) {
		cin >> b[i];
		kooft += b[i];
	}
	if (kooft < 0) {
		cout << "NO" << '\n';
		return 0;
	}
	sort(a, a+n);
	sort(b, b+m);
	reverse(b, b+m);
	memset(dp[0], 1, sizeof(dp[0]));
	Loop (i,1,1<<m)
		sum[i] = sum[i ^ (i & -i)] + b[__builtin_ctz(i)];
	Loop (i,0,n) {
		memset(dp[!(i&1)], 0, sizeof(dp[0]));
		Loop (j,1,1<<m) {
			if (sum[j] == a[i]) {
				int msk = ((1<<m)-1) ^ j;
				int k = 1 << __builtin_popcount(msk);
				if (i&1) {
					Loop (sup, 0, k) {
						int tmp = __builtin_ia32_pdep_si(sup, msk);
						dp[0][tmp ^ j] |= dp[1][tmp];
					}
				} else {
					Loop (sup, 0, k) {
						int tmp = __builtin_ia32_pdep_si(sup, msk);
						dp[1][tmp ^ j] |= dp[0][tmp];
					}
				}
			}
		}
		if (!dp[!(i&1)][(1<<m)-1]) {
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES\n";
}

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