Submission #21,298

2026-01-12 17:57:12

pypy3

Accepted 40/40

46ms

19692 KiB

# UUID: 368a6362-0b14-4c53-9ee5-5016a6bc362b
n = int(input().strip())

if n == 1:
    print(1)
elif n == 2:
    print(2)
elif n == 3:
    print(5)
else:
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    dp[3] = 5

    for i in range(4, n + 1):
        dp[i] = 2 * dp[i-1] + dp[i-3]

    print(dp[n])

	Sum	Test	Verdict		Time	Memory
base	40/40
		1	Accepted	0/0	39ms	19400 KiB
		2	Accepted	0/0	45ms	19404 KiB
		3	Accepted	2/2	39ms	19452 KiB
		4	Accepted	2/2	43ms	19340 KiB
		5	Accepted	2/2	46ms	19692 KiB
		6	Accepted	2/2	43ms	19348 KiB
		7	Accepted	2/2	39ms	19536 KiB
		8	Accepted	3/3	37ms	19376 KiB
		9	Accepted	3/3	43ms	19436 KiB
		10	Accepted	3/3	39ms	19432 KiB
		11	Accepted	3/3	43ms	19364 KiB
		12	Accepted	3/3	37ms	19444 KiB
		13	Accepted	3/3	39ms	19420 KiB
		14	Accepted	3/3	43ms	19436 KiB
		15	Accepted	3/3	37ms	19364 KiB
		16	Accepted	3/3	46ms	19400 KiB
		17	Accepted	3/3	39ms	19408 KiB