結果

問題 No.1318 ABCD quadruplets
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0