結果

問題 No.1318 ABCD quadruplets
ユーザー gew1fw
提出日時 2025-06-12 21:09:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,315 bytes
コンパイル時間 1,715 ms
コンパイル使用メモリ 81,448 KB
実行使用メモリ 183,860 KB
最終ジャッジ日時 2025-06-12 21:11:03
合計ジャッジ時間 8,049 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    M = int(input[1])

    n_values = [0] * (N + 1)

    # Process a
    current = defaultdict(int)
    for a in range(M + 1):
        s = a
        p = a * a
        if p <= N:
            current[(s, p)] += 1

    # Process b
    next_step = defaultdict(int)
    for (s_prev, p_prev), cnt in current.items():
        for b in range(M + 1):
            s_new = s_prev + b
            p_new = p_prev + b * s_prev + b * b
            if p_new > N:
                continue
            next_step[(s_new, p_new)] += cnt
    current = next_step

    # Process c
    next_step = defaultdict(int)
    for (s_prev, p_prev), cnt in current.items():
        for c in range(M + 1):
            s_new = s_prev + c
            p_new = p_prev + c * s_prev + c * c
            if p_new > N:
                continue
            next_step[(s_new, p_new)] += cnt
    current = next_step

    # Process d and update n_values
    for (s_prev, p_prev), cnt in current.items():
        for d in range(M + 1):
            p_new = p_prev + d * s_prev + d * d
            if p_new <= N:
                n_values[p_new] += cnt

    for count in n_values[:N+1]:
        print(count)

if __name__ == "__main__":
    main()
0