結果
問題 |
No.1318 ABCD quadruplets
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:38:19 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,252 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 64,916 KB |
最終ジャッジ日時 | 2025-04-15 23:39:36 |
合計ジャッジ時間 | 4,626 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 19 |
ソースコード
import sys from collections import defaultdict def main(): import math N, M = map(int, sys.stdin.readline().split()) # Initialize DP dp = defaultdict(int) dp[(0, 0)] = 1 for _ in range(4): new_dp = defaultdict(int) for (s, sq), cnt in dp.items(): for x in range(M + 1): new_s = s + x new_sq = sq + x * x new_dp[(new_s, new_sq)] += cnt dp = new_dp # Precompute results for all n from 0 to N result = [0] * (N + 1) for n in range(N + 1): total = 0 max_sum = int(math.isqrt(2 * n)) max_sum = min(max_sum, 4 * M) max_sum2 = int(math.isqrt(8 * n // 5)) # Using integer division for exactness max_sum = min(max_sum, max_sum2) for sum_val in range(0, max_sum + 1): sum_sq = 2 * n - sum_val * sum_val if sum_sq < 0: continue if sum_sq * 4 < sum_val * sum_val: continue if sum_sq > sum_val * sum_val: continue total += dp.get((sum_val, sum_sq), 0) result[n] = total # Output the results for res in result: print(res) if __name__ == '__main__': main()