Submission #640525

#	Time	Username	Problem	Language	Result	Execution time	Memory
640525		ymm	Bank (IZhO14_bank)	C++17	71 / 100	1020 ms	6508 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")
#define _gensup_p(pos, i, j) \
	static inline void gensup_##pos##_##i(int x, int y) \
	{ \
		if ((x & (1<<i)) == 0) \
			gensup_##pos##_##j(x, y); \
		gensup_##pos##_##j(x, y ^ (1<<i)); \
	} \

#define _gensup(i, j) _gensup_p(0, i, j) _gensup_p(1, i, j)
static inline void gensup_0_end(int x, int y)
{
	dp[1][y] |= dp[0][y^x];
}	
static inline void gensup_1_end(int x, int y)
{
	dp[0][y] |= dp[1][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];
	sort(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)];
	void (*gensup[2])(int, int);
	switch(m) {
	case 1 : gensup[0] = gensup_0_0 ; gensup[1] = gensup_1_0 ; break;
	case 2 : gensup[0] = gensup_0_1 ; gensup[1] = gensup_1_1 ; break;
	case 3 : gensup[0] = gensup_0_2 ; gensup[1] = gensup_1_2 ; break;
	case 4 : gensup[0] = gensup_0_3 ; gensup[1] = gensup_1_3 ; break;
	case 5 : gensup[0] = gensup_0_4 ; gensup[1] = gensup_1_4 ; break;
	case 6 : gensup[0] = gensup_0_5 ; gensup[1] = gensup_1_5 ; break;
	case 7 : gensup[0] = gensup_0_6 ; gensup[1] = gensup_1_6 ; break;
	case 8 : gensup[0] = gensup_0_7 ; gensup[1] = gensup_1_7 ; break;
	case 9 : gensup[0] = gensup_0_8 ; gensup[1] = gensup_1_8 ; break;
	case 10: gensup[0] = gensup_0_9 ; gensup[1] = gensup_1_9 ; break;
	case 11: gensup[0] = gensup_0_10; gensup[1] = gensup_1_10; break;
	case 12: gensup[0] = gensup_0_11; gensup[1] = gensup_1_11; break;
	case 13: gensup[0] = gensup_0_12; gensup[1] = gensup_1_12; break;
	case 14: gensup[0] = gensup_0_13; gensup[1] = gensup_1_13; break;
	case 15: gensup[0] = gensup_0_14; gensup[1] = gensup_1_14; break;
	case 16: gensup[0] = gensup_0_15; gensup[1] = gensup_1_15; break;
	case 17: gensup[0] = gensup_0_16; gensup[1] = gensup_1_16; break;
	case 18: gensup[0] = gensup_0_17; gensup[1] = gensup_1_17; break;
	case 19: gensup[0] = gensup_0_18; gensup[1] = gensup_1_18; break;
	default: gensup[0] = gensup_0_19; gensup[1] = gensup_1_19; break;
	}
	Loop (i,0,n) {
		memset(dp[!(i&1)], 0, sizeof(dp[0]));
		Loop (j,1,1<<m) {
			if (sum[j] == a[i])
				gensup[i&1](j, 0);
		}
	}
	cout << (dp[n&1][(1<<m)-1]? "YES": "NO") << '\n';
}

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