結果
問題 |
No.1634 Sorting Integers (Multiple of K) Hard
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:51:30 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,205 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,624 KB |
実行使用メモリ | 599,760 KB |
最終ジャッジ日時 | 2025-06-12 15:51:41 |
合計ジャッジ時間 | 7,526 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 4 MLE * 1 -- * 23 |
ソースコード
import sys from functools import lru_cache def main(): sys.setrecursionlimit(1 << 25) n, k = map(int, sys.stdin.readline().split()) counts = list(map(int, sys.stdin.readline().split())) # Precompute the digits that are available and their counts digits = [(i+1, counts[i]) for i in range(9) if counts[i] > 0] # Convert counts into a tuple for easier handling initial_counts = tuple(counts) @lru_cache(maxsize=None) def dp(current_counts, rem): # Check if all counts are zero (base case) if all(c == 0 for c in current_counts): return 1 if rem == 0 else 0 total = 0 for i in range(9): if current_counts[i] == 0: continue # Create new counts by decrementing the ith digit new_counts = list(current_counts) new_counts[i] -= 1 new_counts_tuple = tuple(new_counts) # Compute the new remainder new_rem = (rem * 10 + (i + 1)) % k total += dp(new_counts_tuple, new_rem) return total result = dp(initial_counts, 0) print(result) if __name__ == "__main__": main()