結果
問題 |
No.1318 ABCD quadruplets
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:30:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 963 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 64,856 KB |
最終ジャッジ日時 | 2025-06-12 21:30:23 |
合計ジャッジ時間 | 5,257 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 19 |
ソースコード
import sys from collections import defaultdict def main(): N, M = map(int, sys.stdin.readline().split()) # Initialize the DP state for 0 variables state = defaultdict(int) state[(0, 0)] = 1 # Process each of the four variables for _ in range(4): new_state = defaultdict(int) for (t, u), cnt in state.items(): for x in range(0, M + 1): new_t = t + x new_u = u + x * x new_state[(new_t, new_u)] += cnt state = new_state # Now, for each n from 0 to N, compute f(n, M) for n in range(N + 1): res = 0 max_t = int((2 * n) ** 0.5) max_t = min(max_t, 4 * M) # Since a + b + c + d can't exceed 4*M for t in range(0, max_t + 1): u = 2 * n - t * t if u < 0 or u > 4 * M * M: continue res += state.get((t, u), 0) print(res) if __name__ == "__main__": main()