結果
問題 |
No.1318 ABCD quadruplets
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:10:33 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 855 bytes |
コンパイル時間 | 363 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 233,656 KB |
最終ジャッジ日時 | 2025-06-12 21:12:04 |
合計ジャッジ時間 | 4,995 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 19 |
ソースコード
from collections import defaultdict def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) M = int(data[1]) dp = defaultdict(int) dp[(0, 0)] = 1 # Initial state: sum=0, sum_sq=0 for _ in range(4): new_dp = defaultdict(int) for (current_sum, sum_sq), count in dp.items(): for x in range(M + 1): new_sum = current_sum + x new_sum_sq = sum_sq + x * x new_dp[(new_sum, new_sum_sq)] += count dp = new_dp ans = [0] * (N + 1) for (s, k), cnt in dp.items(): total = s * s + k if total % 2 != 0: continue n = total // 2 if 0 <= n <= N: ans[n] += cnt for count in ans: print(count) if __name__ == '__main__': main()