結果

問題 No.2744 Power! or +1
コンテスト
ユーザー detteiuu
提出日時 2026-10-03 16:04:35
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 814 ms / 3,000 ms
+ 938µs
コード長 1,213 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 62 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 119,308 KB
最終ジャッジ日時 2026-10-03 16:04:42
合計ジャッジ時間 4,821 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import heappush, heappop

def factorial(n, MOD):
    F = [1]
    for i in range(1, n+1):
        F.append(F[-1]*i%MOD)
    return F

INF = 1<<60

N, A, B, C = map(int, input().split())

base = A*N
F = factorial(N, N)
start = INF
p = 1
for i in range(1, N+1):
    p *= i
    if N <= p:
        start = i
        break

visited = [False]*N
dist = [INF]*N
dist[1] = 0
que = [(0, 1)]
while que:
    _, n = heappop(que)
    if visited[n]: continue
    visited[n] = True
    if dist[n]+A < dist[(n+1)%N]:
        dist[(n+1)%N] = dist[n]+A
        heappush(que, (dist[(n+1)%N], (n+1)%N))
    v = n
    cost = B
    flag = False
    while cost <= base:
        if dist[n]+cost < dist[v]:
            dist[v] = dist[n]+cost
            heappush(que, (dist[v], v))
        if flag and dist[n]+cost+C < dist[0]:
            dist[0] = dist[n]+cost+C
            heappush(que, (dist[0], 0))
        v *= n
        if N <= v: flag = True
        v %= N
        cost *= B
    if dist[n]+C < dist[F[n]]:
        dist[F[n]] = dist[n]+C
        heappush(que, (dist[F[n]], F[n]))
        if start <= n and dist[n]+C+C < dist[0]:
            dist[0] = dist[n]+C+C
            heappush(que, (dist[F[n]], 0))

print(dist[0])
0