Submission #768336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768336	2023-06-27T23:50:57 Z	iamjiamingliu	Bank (IZhO14_bank)	PyPy 3	71 / 100	1000 ms	26356 KB

bank

input()
salaries = list(map(int, input().split()))
notes = list(map(int, input().split()))

if len(salaries) > len(notes):
    print('NO')
    exit()

combo_to_form = [[] for _ in range(len(salaries))]
for i, val in enumerate(salaries):
    for subset in range(1 << len(notes)):
        if sum(notes[j] for j in range(subset.bit_length()) if (1 << j) & subset) == val:
            combo_to_form[i].append(subset)
    if not combo_to_form[i]:
        print('NO')
        exit()

prev_subsets = {(1 << len(notes)) - 1}
for i in range(len(salaries)):
    new_subsets = set()
    for prev in prev_subsets:
        for needed in combo_to_form[i]:
            if (prev & needed) == needed:
                new_subsets.add(prev - needed)
    if not new_subsets:
        print('NO')
        exit()
    prev_subsets = new_subsets

print('YES')

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	18148 KB	Output is correct
2	Correct	30 ms	18244 KB	Output is correct
3	Correct	48 ms	20384 KB	Output is correct
4	Correct	72 ms	22764 KB	Output is correct
5	Correct	473 ms	25104 KB	Output is correct
6	Correct	47 ms	20352 KB	Output is correct
7	Correct	59 ms	22084 KB	Output is correct
8	Correct	489 ms	25568 KB	Output is correct
9	Correct	476 ms	25152 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	24616 KB	Output is correct
2	Correct	75 ms	23916 KB	Output is correct
3	Correct	71 ms	23476 KB	Output is correct
4	Correct	77 ms	24492 KB	Output is correct
5	Correct	82 ms	24520 KB	Output is correct
6	Correct	76 ms	24144 KB	Output is correct
7	Correct	76 ms	24104 KB	Output is correct
8	Correct	81 ms	24356 KB	Output is correct
9	Correct	76 ms	24048 KB	Output is correct
10	Correct	76 ms	24488 KB	Output is correct

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	25896 KB	Output is correct
2	Correct	143 ms	25908 KB	Output is correct
3	Correct	148 ms	25916 KB	Output is correct
4	Correct	68 ms	22572 KB	Output is correct
5	Correct	148 ms	25908 KB	Output is correct
6	Correct	70 ms	22564 KB	Output is correct
7	Correct	118 ms	25888 KB	Output is correct
8	Correct	119 ms	25932 KB	Output is correct
9	Correct	140 ms	25844 KB	Output is correct
10	Correct	139 ms	25876 KB	Output is correct
11	Correct	64 ms	22504 KB	Output is correct

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	18148 KB	Output is correct
2	Correct	30 ms	18244 KB	Output is correct
3	Correct	48 ms	20384 KB	Output is correct
4	Correct	72 ms	22764 KB	Output is correct
5	Correct	473 ms	25104 KB	Output is correct
6	Correct	47 ms	20352 KB	Output is correct
7	Correct	59 ms	22084 KB	Output is correct
8	Correct	489 ms	25568 KB	Output is correct
9	Correct	476 ms	25152 KB	Output is correct
10	Correct	79 ms	24616 KB	Output is correct
11	Correct	75 ms	23916 KB	Output is correct
12	Correct	71 ms	23476 KB	Output is correct
13	Correct	77 ms	24492 KB	Output is correct
14	Correct	82 ms	24520 KB	Output is correct
15	Correct	76 ms	24144 KB	Output is correct
16	Correct	76 ms	24104 KB	Output is correct
17	Correct	81 ms	24356 KB	Output is correct
18	Correct	76 ms	24048 KB	Output is correct
19	Correct	76 ms	24488 KB	Output is correct
20	Correct	137 ms	25896 KB	Output is correct
21	Correct	143 ms	25908 KB	Output is correct
22	Correct	148 ms	25916 KB	Output is correct
23	Correct	68 ms	22572 KB	Output is correct
24	Correct	148 ms	25908 KB	Output is correct
25	Correct	70 ms	22564 KB	Output is correct
26	Correct	118 ms	25888 KB	Output is correct
27	Correct	119 ms	25932 KB	Output is correct
28	Correct	140 ms	25844 KB	Output is correct
29	Correct	139 ms	25876 KB	Output is correct
30	Correct	64 ms	22504 KB	Output is correct
31	Correct	938 ms	26356 KB	Output is correct
32	Execution timed out	1084 ms	26004 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-