結果

問題 No.1956 猫の額
ユーザー gew1fw
提出日時 2025-06-12 18:08:31
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 979 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 117,636 KB
最終ジャッジ日時 2025-06-12 18:10:25
合計ジャッジ時間 5,052 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, M, C = map(int, input().split())
A = list(map(int, input().split()))
sumA = sum(A)

if C == 0:
    print(' '.join(['0'] * sumA))
    exit()

# Initialize DP and max_s arrays
dp = [[0] * (sumA + 1) for _ in range(C + 1)]
dp[0][0] = 1
max_s = [0] * (C + 1)

for a in A:
    # Iterate from C down to 1 to avoid overwriting data we need to read
    for c in range(C, 0, -1):
        prev_c = c - 1
        prev_max = max_s[prev_c]
        if prev_max == 0 and dp[prev_c][0] == 0:
            continue  # Skip if no previous entries
        
        new_max = max(max_s[c], prev_max + a)
        current_dp = dp[c]
        prev_dp = dp[prev_c]
        
        for s in range(prev_max + 1):
            if prev_dp[s]:
                new_s = s + a
                current_dp[new_s] = (current_dp[new_s] + prev_dp[s]) % M
        
        max_s[c] = new_max

# Prepare the result
result = []
for s in range(1, sumA + 1):
    result.append(str(dp[C][s] % M))

print(' '.join(result))
0