Submission #13537543


Source Code Expand

Copy
import sys
from functools import lru_cache

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

def solve(N, A, B, C, D):
    INF = 10**18

    @lru_cache(None)
    def f(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        ret = D * N
        q, r = divmod(N, 2)
        if r == 0:
            ret = min(ret, f(q) + A)
        else:
            ret = min(ret, f(q) + A + D, f(q + 1) + A + D)
        q, r = divmod(N, 3)
        if r == 0:
            ret = min(ret, f(q) + B)
        elif r == 1:
            ret = min(ret, f(q) + B + D)
        else:
            ret = min(ret, f(q + 1) + B + D)
        q, r = divmod(N, 5)
        if r == 0:
            ret = min(ret, f(q) + C)
        elif r == 1:
            ret = min(ret, f(q) + C + D)
        elif r == 2:
            ret = min(ret, f(q) + C + D + D)
        elif r == 3:
            ret = min(ret, f(q + 1) + C + D + D)
        else:
            ret = min(ret, f(q + 1) + C + D)
        return ret

    return f(N)

T = int(readline())
for _ in range(T):
    n, a, b, c, d = map(int, readline().split())
    print(solve(n, a, b, c, d))

Submission Info

Submission Time
Task A - Pay to Win
User maspy
Language Python (3.8.2)
Score 400
Code Size 1235 Byte
Status
Exec Time 181 ms
Memory 20320 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt
All 400 / 400 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, example0.txt
Case Name Status Exec Time Memory
000.txt 22 ms 9312 KB
001.txt 21 ms 9416 KB
002.txt 22 ms 9532 KB
003.txt 24 ms 9328 KB
004.txt 22 ms 9568 KB
005.txt 181 ms 20320 KB
006.txt 125 ms 15804 KB
007.txt 147 ms 16404 KB
008.txt 129 ms 15820 KB
example0.txt 48 ms 11424 KB