結果
問題 |
No.1318 ABCD quadruplets
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:43:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,221 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 210,816 KB |
最終ジャッジ日時 | 2025-06-12 16:44:26 |
合計ジャッジ時間 | 5,069 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 10 TLE * 1 -- * 19 |
ソースコード
import sys from collections import defaultdict def main(): N, M = map(int, sys.stdin.readline().split()) # Precompute F_ab and F_cd F_ab = defaultdict(lambda: defaultdict(int)) for a in range(M + 1): for b in range(M + 1): x = a + b t = a*a + b*b F_ab[x][t] += 1 F_cd = F_ab # F_cd is the same as F_ab # Compute convolution cnt = defaultdict(lambda: defaultdict(int)) for x1 in F_ab: for t1 in F_ab[x1]: count1 = F_ab[x1][t1] for x2 in F_cd: for t2 in F_cd[x2]: count2 = F_cd[x2][t2] x = x1 + x2 t = t1 + t2 cnt[x][t] += count1 * count2 # Compute the result result = [0] * (N + 1) for n in range(N + 1): total = 0 max_S = int((2 * n) ** 0.5) for S in range(0, max_S + 1): T = 2 * n - S * S if T < 0: continue if S in cnt and T in cnt[S]: total += cnt[S][T] result[n] = total for res in result: print(res) print() # Ensure a newline at the end if __name__ == '__main__': main()