Submission #640467

#	Time	Username	Problem	Language	Result	Execution time	Memory
640467		ymm	Bank (IZhO14_bank)	C++17	71 / 100	1024 ms	25952 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[N+1][1<<N];
int a[N], b[N];
int sum[1<<N];
int n, m;

#pragma GCC optimize("O3")
extern "C" {
#define _gensup(i, i2, j) \
	__attribute((naked)) \
	static inline void gensup_##i(int x, int y, int pos) \
	{ \
	asm( \
	"	testl   $"#i2", %edi\n" \
	"	je      .MY_L"#i"\n" \
	"	xorl    $"#i2", %esi\n" \
	"	jmp     gensup_"#j"\n" \
	"	.p2align 4,,10\n" \
	"	.p2align 3\n" \
	".MY_L"#i":\n" \
	"	subq    $4, %rsp\n" \
	"	.cfi_def_cfa_offset 16\n" \
	"	movl    %esi, (%rsp)\n" \
	"	call    gensup_"#j"\n" \
	"	movl    (%rsp), %esi\n" \
	"	addq    $4, %rsp\n" \
	"	.cfi_def_cfa_offset 8\n" \
	"	xorl    $"#i2", %esi\n" \
	"	jmp     gensup_"#j"\n" \
	); \
	} \

__attribute__((naked))
void gensup_end(int x, int y, int pos)
{
	asm(
	"leal    1(%rdx), %eax\n"
	"movl    %edi, %r8d\n"
	"movslq  %edx, %rdx\n"
	"movslq  %esi, %rdi\n"
	"cltq\n"
	"leaq    dp(%rip), %rcx\n"
	"salq    $20, %rdx\n"
	"xorl    %r8d, %esi\n"
	"salq    $20, %rax\n"
	"movslq  %esi, %rsi\n"
	"addq    %rcx, %rax\n"
	"addq    %rdx, %rcx\n"
	"movzbl  (%rcx,%rsi), %ecx\n"
	"orb     %cl, (%rax,%rdi)\n"
	"xorl    %r8d, %esi\n"
	"movl    %r8d, %edi\n"
	"sar     $20, %rdx\n"
	"ret\n"
	);
}	

_gensup(0 , 1, end)
_gensup(1 , 2, 0)
_gensup(2 , 4, 1)
_gensup(3 , 8, 2)
_gensup(4 , 16, 3)
_gensup(5 , 32, 4)
_gensup(6 , 64, 5)
_gensup(7 , 128, 6)
_gensup(8 , 256, 7)
_gensup(9 , 512, 8)
_gensup(10, 1024, 9)
_gensup(11, 2048, 10)
_gensup(12, 4096, 11)
_gensup(13, 8192, 12)
_gensup(14, 16384, 13)
_gensup(15, 32768, 14)
_gensup(16, 65536, 15)
_gensup(17, 131072, 16)
_gensup(18, 262144, 17)
_gensup(19, 524288, 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];
	memset(dp[0], 1, sizeof(dp[0]));
	Loop (i,1,1<<m)
		sum[i] = sum[i ^ (i & -i)] + b[__builtin_ctz(i)];
	void (*gensup)(int, int, int);
	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) {
		Loop (j,0,1<<m) {
			if (sum[j] == a[i]) {
				gensup(j, 0, i);
			}
		}
	}
	cout << (dp[n][(1<<m)-1]? "YES": "NO") << '\n';
}

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