結果

問題 No.1956 猫の額
ユーザー lam6er
提出日時 2025-04-15 21:11:18
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,508 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 117,728 KB
最終ジャッジ日時 2025-04-15 21:17:46
合計ジャッジ時間 35,722 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 MLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    C = int(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    A.sort()
    
    min_s = [0] * (C + 1)
    max_s = [0] * (C + 1)
    
    # Calculate min_s for each c
    for c in range(1, C + 1):
        if c > N:
            min_s[c] = 0
        else:
            min_s[c] = sum(A[:c])
    
    # Calculate max_s for each c
    for c in range(1, C + 1):
        if c > N:
            max_s[c] = 0
        else:
            max_s[c] = sum(A[-c:])
    
    # Initialize dp array for each c
    dp = []
    for c in range(C + 1):
        if c > N:
            dp.append([])
            continue
        current_min = min_s[c]
        current_max = max_s[c]
        size = current_max - current_min + 1 if current_max >= current_min else 0
        dp.append([0] * size)
    
    # Base case: c=0, s=0
    if C >= 0 and 0 <= 0 <= 0:  # c=0's min and max are 0
        dp[0][0] = 1
    
    for a in A:
        for c in range(C, 0, -1):
            if c > N:
                continue
            current_min = min_s[c]
            current_max = max_s[c]
            prev_min = min_s[c-1]
            prev_max = max_s[c-1]
            if c-1 > N or prev_min > prev_max:
                continue  # no possible sum for c-1
            
            for s in range(current_max, current_min - 1, -1):
                s_prev = s - a
                if s_prev < prev_min or s_prev > prev_max:
                    continue
                idx_prev = s_prev - prev_min
                idx_current = s - current_min
                if len(dp[c-1]) <= idx_prev:
                    continue
                dp[c][idx_current] = (dp[c][idx_current] + dp[c-1][idx_prev]) % M
    
    S = sum(A)
    result = []
    for s in range(1, S + 1):
        if C > N:
            result.append(0)
            continue
        if C < 0:
            result.append(0)
            continue
        c = C
        if c > N:
            result.append(0)
            continue
        if min_s[c] > max_s[c]:
            result.append(0)
            continue
        if s < min_s[c] or s > max_s[c]:
            result.append(0)
        else:
            idx = s - min_s[c]
            if idx >= len(dp[c]):
                result.append(0)
            else:
                result.append(dp[c][idx] % M)
    
    print(' '.join(map(str, result)))

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