結果
問題 | No.2744 Power! or +1 |
ユーザー | shobonvip |
提出日時 | 2024-04-21 09:59:41 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 746 bytes |
コンパイル時間 | 599 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 645,584 KB |
最終ジャッジ日時 | 2024-04-21 09:59:56 |
合計ジャッジ時間 | 14,699 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | AC | 593 ms
132,200 KB |
testcase_02 | AC | 198 ms
86,764 KB |
testcase_03 | AC | 241 ms
90,696 KB |
testcase_04 | AC | 344 ms
124,228 KB |
testcase_05 | MLE | - |
testcase_06 | AC | 1,035 ms
276,072 KB |
testcase_07 | AC | 40 ms
52,608 KB |
testcase_08 | AC | 1,015 ms
194,808 KB |
testcase_09 | AC | 73 ms
70,016 KB |
testcase_10 | AC | 92 ms
76,540 KB |
ソースコード
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])