結果

問題 No.1318 ABCD quadruplets
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:31:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,079 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 253,272 KB
最終ジャッジ日時 2025-06-12 16:31:28
合計ジャッジ時間 5,459 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N, M = map(int, sys.stdin.readline().split())
    
    # Initialize DP after processing d
    dp = defaultdict(lambda: defaultdict(int))
    for d in range(M + 1):
        sum_S = d * d
        if sum_S > N:
            continue
        sum_prev = d
        dp[sum_S][sum_prev] += 1
    
    # Process c
    new_dp = defaultdict(lambda: defaultdict(int))
    for sum_S_prev in dp:
        for sum_prev_prev, count in dp[sum_S_prev].items():
            for c in range(M + 1):
                contribution = c * (c + sum_prev_prev)
                new_sum_S = sum_S_prev + contribution
                if new_sum_S > N:
                    continue
                new_sum_prev = sum_prev_prev + c
                new_dp[new_sum_S][new_sum_prev] += count
    dp = new_dp
    
    # Process b
    new_dp = defaultdict(lambda: defaultdict(int))
    for sum_S_prev in dp:
        for sum_prev_prev, count in dp[sum_S_prev].items():
            for b in range(M + 1):
                contribution = b * (b + sum_prev_prev)
                new_sum_S = sum_S_prev + contribution
                if new_sum_S > N:
                    continue
                new_sum_prev = sum_prev_prev + b
                new_dp[new_sum_S][new_sum_prev] += count
    dp = new_dp
    
    # Process a
    new_dp = defaultdict(lambda: defaultdict(int))
    for sum_S_prev in dp:
        for sum_prev_prev, count in dp[sum_S_prev].items():
            for a in range(M + 1):
                contribution = a * (a + sum_prev_prev)
                new_sum_S = sum_S_prev + contribution
                if new_sum_S > N:
                    continue
                new_sum_prev = sum_prev_prev + a
                new_dp[new_sum_S][new_sum_prev] += count
    dp = new_dp
    
    # Collect results
    result = [0] * (N + 1)
    for sum_S in dp:
        if sum_S <= N:
            total = sum(dp[sum_S].values())
            result[sum_S] = total
    
    for n in range(N + 1):
        print(result[n])

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