結果

問題 No.1956 猫の額
ユーザー lam6er
提出日時 2025-03-20 21:08:06
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,739 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 83,024 KB
実行使用メモリ 117,720 KB
最終ジャッジ日時 2025-03-20 21:08:24
合計ジャッジ時間 6,063 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    C = int(data[idx])
    idx += 1
    A = list(map(int, data[idx:idx+n]))
    sumA_total = sum(A)
    
    # Initialize DP table
    dp = [[0] * (sumA_total + 1) for _ in range(C+1)]
    dp[0][0] = 1  # Base case: 0 elements sum to 0
    
    # Track the maximum possible sum for each count of selected elements
    current_max_s = [-1] * (C + 1)
    current_max_s[0] = 0  # For 0 elements, sum is 0
    
    for a in A:
        new_max_s = current_max_s.copy()
        for c in range(C, 0, -1):
            prev_c = c - 1
            if current_max_s[prev_c] == -1:
                continue  # No way to select prev_c elements, skip
            possible_max = current_max_s[prev_c] + a
            if possible_max > sumA_total:
                possible_max = sumA_total
            # Determine the range of sums to update
            end_s = min(possible_max, sumA_total)
            start_s = a
            # Iterate from end_s down to start_s to avoid using the same element multiple times
            dp_prev = dp[prev_c]
            dp_c = dp[c]
            for s in range(end_s, start_s - 1, -1):
                if dp_prev[s - a]:
                    dp_c[s] = (dp_c[s] + dp_prev[s - a]) % M
            # Update new_max_s for current c if possible_max is larger
            new_max_s[c] = max(new_max_s[c], possible_max)
        current_max_s = new_max_s
    
    # Collect results from s=1 to sumA_total
    result = []
    for s in range(1, sumA_total + 1):
        result.append(str(dp[C][s] % M))
    print(' '.join(result))

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