Submission #17958988


Source Code Expand

Copy
import sys
import numpy as np
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@lru_cache(None)
def f(X, i):
    # i 番目の硬貨よりうしろだけを使う
    if i == N - 1:
        return 1 * (X >= 0)
    a, b = A[i], A[i + 1]
    assert X % a == 0
    if X % b == 0:
        return f(X, i + 1)
    X -= X % b
    return f(X, i + 1) + f(X + b, i + 1)

N, X, *A = map(int, read().split())

print(f(X, 0))

Submission Info

Submission Time
Task F - Valid payments
User maspy
Language Python (3.8.2)
Score 600
Code Size 524 Byte
Status AC
Exec Time 117 ms
Memory 27152 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All answer_big_00.txt, border_00.txt, border_01.txt, border_02.txt, border_03.txt, border_04.txt, border_05.txt, border_06.txt, border_07.txt, border_08.txt, border_09.txt, handmade_00.txt, handmade_01.txt, handmade_02.txt, handmade_03.txt, longest_00.txt, longest_01.txt, longest_02.txt, longest_03.txt, longest_04.txt, overflow_killer_00.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
answer_big_00.txt AC 117 ms 27136 KB
border_00.txt AC 112 ms 27124 KB
border_01.txt AC 113 ms 26672 KB
border_02.txt AC 111 ms 26992 KB
border_03.txt AC 108 ms 26964 KB
border_04.txt AC 114 ms 26820 KB
border_05.txt AC 113 ms 26572 KB
border_06.txt AC 113 ms 26848 KB
border_07.txt AC 113 ms 27152 KB
border_08.txt AC 112 ms 27120 KB
border_09.txt AC 113 ms 26948 KB
handmade_00.txt AC 111 ms 26852 KB
handmade_01.txt AC 113 ms 26972 KB
handmade_02.txt AC 111 ms 26976 KB
handmade_03.txt AC 111 ms 27076 KB
longest_00.txt AC 110 ms 26904 KB
longest_01.txt AC 112 ms 26964 KB
longest_02.txt AC 112 ms 26836 KB
longest_03.txt AC 113 ms 26884 KB
longest_04.txt AC 112 ms 26884 KB
overflow_killer_00.txt AC 107 ms 26796 KB
random_00.txt AC 111 ms 26844 KB
random_01.txt AC 113 ms 26568 KB
random_02.txt AC 110 ms 26920 KB
random_03.txt AC 113 ms 26920 KB
random_04.txt AC 112 ms 26516 KB
random_05.txt AC 111 ms 27076 KB
random_06.txt AC 115 ms 26864 KB
random_07.txt AC 110 ms 26924 KB
random_08.txt AC 109 ms 26940 KB
random_09.txt AC 110 ms 27104 KB
sample_01.txt AC 111 ms 26764 KB
sample_02.txt AC 114 ms 26936 KB
sample_03.txt AC 112 ms 26508 KB
sample_04.txt AC 115 ms 27136 KB