結果

問題 No.1318 ABCD quadruplets
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:34:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,197 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 182,876 KB
最終ジャッジ日時 2025-03-20 20:35:54
合計ジャッジ時間 7,440 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, M = map(int, sys.stdin.readline().split())
    f = [0] * (N + 1)
    
    # DP1: Processing d
    dp1 = defaultdict(int)
    for d in range(M + 1):
        t = d * d
        if t <= N:
            dp1[(d, t)] += 1
    
    # DP2: Processing c
    dp2 = defaultdict(int)
    for (s_prev, t_prev), cnt in dp1.items():
        for c in range(M + 1):
            new_s = s_prev + c
            new_t = t_prev + c * new_s
            if new_t > N:
                continue
            dp2[(new_s, new_t)] += cnt
    
    # DP3: Processing b
    dp3 = defaultdict(int)
    for (s_prev, t_prev), cnt in dp2.items():
        for b in range(M + 1):
            new_s = s_prev + b
            new_t = t_prev + b * new_s
            if new_t > N:
                continue
            dp3[(new_s, new_t)] += cnt
    
    # Processing a and accumulate results into f
    for (s_prev, t_prev), cnt in dp3.items():
        for a in range(M + 1):
            new_t = t_prev + a * (s_prev + a)
            if new_t <= N:
                f[new_t] += cnt
    
    for n in range(N + 1):
        print(f[n])
    
if __name__ == "__main__":
    main()
0