結果
問題 |
No.1318 ABCD quadruplets
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:59:44 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,197 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,548 KB |
実行使用メモリ | 183,012 KB |
最終ジャッジ日時 | 2025-03-20 19:00:16 |
合計ジャッジ時間 | 7,933 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 TLE * 1 -- * 16 |
ソースコード
import sys from collections import defaultdict def main(): N, M = map(int, sys.stdin.readline().split()) f = [0] * (N + 1) # DP1: Processing d dp1 = defaultdict(int) for d in range(M + 1): t = d * d if t <= N: dp1[(d, t)] += 1 # DP2: Processing c dp2 = defaultdict(int) for (s_prev, t_prev), cnt in dp1.items(): for c in range(M + 1): new_s = s_prev + c new_t = t_prev + c * new_s if new_t > N: continue dp2[(new_s, new_t)] += cnt # DP3: Processing b dp3 = defaultdict(int) for (s_prev, t_prev), cnt in dp2.items(): for b in range(M + 1): new_s = s_prev + b new_t = t_prev + b * new_s if new_t > N: continue dp3[(new_s, new_t)] += cnt # Processing a and accumulate results into f for (s_prev, t_prev), cnt in dp3.items(): for a in range(M + 1): new_t = t_prev + a * (s_prev + a) if new_t <= N: f[new_t] += cnt for n in range(N + 1): print(f[n]) if __name__ == "__main__": main()