結果
問題 |
No.2744 Power! or +1
|
ユーザー |
![]() |
提出日時 | 2024-04-21 09:59:41 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 746 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 1,301,640 KB |
最終ジャッジ日時 | 2024-10-13 08:47:05 |
合計ジャッジ時間 | 8,717 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | MLE * 1 -- * 8 |
ソースコード
n,a,b,c = map(int,input().split()) dp = [10 ** 18] * 2 * n dp[1] = 0 ikeru = [[] for i in range(2 * n)] costb = [b ** k for k in range(55)] kaijo = 1 for i in range(1, 2 * n): kaijo *= i if kaijo >= n: kaijo = kaijo % n + n ikeru[i].append((kaijo, c)) tar = i * i if tar >= n: tar = tar % n + n for k in range(2, 50): if costb[k] >= 10 ** 11: break ikeru[i].append((tar, costb[k])) tar *= i if tar >= n: tar = tar % n + n tar = i + 1 if tar >= n: tar = tar % n + n ikeru[i].append((tar, a)) import heapq pq = [] heapq.heappush(pq, (0, 1)) while pq: tmp, i = heapq.heappop(pq) if tmp > dp[i]: continue for j, cost in ikeru[i]: if cost + tmp < dp[j]: dp[j] = cost + tmp heapq.heappush(pq, (dp[j], j)) print(dp[n])