# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
545673 | AA_Surely | Bank (IZhO14_bank) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("unroll-loops,O3");
#pragma GCC target("avx2");
#include <bits/stdc++.h>
#define FOR(i,x,n) for(int i=x; i<n; i++)
#define F0R(i,n) FOR(i,0,n)
#define ROF(i,x,n) for(int i=n-1; i>=x; i--)
#define R0F(i,n) ROF(i,0,n)
#define WTF cout << "WTF" << endl
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define F first
#define S second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int MAXN = 22;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;
int n, m, ns[2][MAXN];
int ps[MAXN], sum[1 << MAXN];
int dp[MAXN][1 << MAXN];
int main() {
IOS;
cin >> n >> m;
FOR(i, 1, n + 1) {
cin >> ns[0][i];
ps[i] = ps[i - 1] + ns[0][i];
}
F0R(i, m) cin >> ns[1][i];
FOR(mask, 1, (1 << m)) F0R(b, m) if ((mask >> b) & 1)
sum[mask] += ns[1][b];
F0R(i, (1 << m)) dp[0][i] = 1;
FOR(i, 1, n + 1) FOR(mask, 1, (1 << m)) {
F0R(b, m) if ((mask >> b) & 1) dp[i][mask] |= dp[i][mask ^ (1 << b)];
if (ps[i] == sum[mask] && dp[i - 1][mask]) dp[i][mask] = 1;
}
cout << (dp[n][(1 << m) - 1] ? "YES" : "NO");
}