| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 640488 | ymm | 은행 (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.
#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;
bitset<1<<N> dp[2];
int a[N], b[N];
int sum[1<<N];
int n, m;
#pragma GCC optimize("O3")
#define _gensup(i, j) \
static inline void gensup_##i(int x, int y, bool pos) \
{ \
if ((x & (1<<i)) == 0) \
gensup_##j(x, y, pos); \
gensup_##j(x, y ^ (1<<i), pos); \
} \
static inline void gensup_end(int x, int y, bool pos)
{
dp[!pos][y] |= dp[pos][y^x];
}
_gensup(0 , end)
_gensup(1 , 0)
_gensup(2 , 1)
_gensup(3 , 2)
_gensup(4 , 3)
_gensup(5 , 4)
_gensup(6 , 5)
_gensup(7 , 6)
_gensup(8 , 7)
_gensup(9 , 8)
_gensup(10, 9)
_gensup(11, 10)
_gensup(12, 11)
_gensup(13, 12)
_gensup(14, 13)
_gensup(15, 14)
_gensup(16, 15)
_gensup(17, 16)
_gensup(18, 17)
_gensup(19, 18)
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n)
cin >> a[i];
Loop (i,0,m)
cin >> b[i];
dp[0].set();
Loop (i,1,1<<m)
sum[i] = sum[i ^ (i & -i)] + b[__builtin_ctz(i)];
void (*gensup)(int, int, bool);
switch(m) {
case 1 : gensup = gensup_0 ; break;
case 2 : gensup = gensup_1 ; break;
case 3 : gensup = gensup_2 ; break;
case 4 : gensup = gensup_3 ; break;
case 5 : gensup = gensup_4 ; break;
case 6 : gensup = gensup_5 ; break;
case 7 : gensup = gensup_6 ; break;
case 8 : gensup = gensup_7 ; break;
case 9 : gensup = gensup_8 ; break;
case 10: gensup = gensup_9 ; break;
case 11: gensup = gensup_10; break;
case 12: gensup = gensup_11; break;
case 13: gensup = gensup_12; break;
case 14: gensup = gensup_13; break;
case 15: gensup = gensup_14; break;
case 16: gensup = gensup_15; break;
case 17: gensup = gensup_16; break;
case 18: gensup = gensup_17; break;
case 19: gensup = gensup_18; break;
default: gensup = gensup_19; break;
}
Loop (i,0,n) {
dp[!(i&1)].reset();
Loop (j,0,1<<m) {
if (sum[j] == a[i]) {
gensup(j, 0, i&1);
}
}
}
cout << (dp[n&1][(1<<m)-1]? "YES": "NO") << '\n';
}