結果

問題 No.3368 トッピング
コンテスト
ユーザー iro_
提出日時 2025-10-29 16:55:30
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,049 bytes
コンパイル時間 153 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2025-11-17 20:36:21
合計ジャッジ時間 1,588 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # 入力の読み込み
    try:
        N, M, X, C = map(int, sys.stdin.readline().split())
        A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    except ValueError:
        print("入力エラー: N, M, X, C または A の形式が正しくありません。")
        return

    # -----------------------------------------------------------------
    # 判定関数: 満足度の最小値を K 以上にできるか？
    # -----------------------------------------------------------------
    def is_possible(K):
        
        # --- N=1 (エッジケース) ---
        if N == 1:
            if X > 0:
                return False  # ペナルティは発生し得ない
            
            max_score = -1
            for j in range(M):
                max_score = max(max_score, A[0][j])
            return max_score >= K

        # --- N >= 2 (DP) ---
        
        # DPテーブル: dp_curr[j][k]
        # 位置 i-1 がカテゴリ j, 位置 i がカテゴリ k のときの、
        # 位置 1 から i-1 までのペナルティ発生位置の最大総数
        # 到達不能は -1 で初期化
        dp_curr = [[-1] * M for _ in range(M)]

        # --- 初期化 (i=2) ---
        # j = cat[1], k = cat[2]
        for j in range(M):
            for k in range(M):
                is_penalized_1 = (j == k)
                score_1 = A[0][j] - (C if is_penalized_1 else 0)
                
                if score_1 >= K:
                    dp_curr[j][k] = 1 if is_penalized_1 else 0

        # --- DP遷移 (i = 3 to N) ---
        for i in range(3, N + 1):
            dp_prev = dp_curr
            dp_curr = [[-1] * M for _ in range(M)]
            
            # i-1 のスコアインデックス (A[score_idx])
            score_idx = i - 2 

            # DP遷移を高速化するための前計算 O(M^2)
            # precalc_no_penalty[j]:
            #   cat[i-2] != j かつ score[i-1] >= K を満たす j_prev からの
            #   max(dp_prev[j_prev][j] + 0)
            # precalc_with_penalty[j]:
            #   cat[i-2] == j かつ score[i-1] >= K を満たす j_prev からの
            #   max(dp_prev[j_prev][j] + 1)
            
            precalc_no_penalty = [-1] * M
            precalc_with_penalty = [-1] * M
            
            for j in range(M): # cat[i-1]
                val_no_penalty = A[score_idx][j]
                val_with_penalty = A[score_idx][j] - C
                
                max_A = -1 # (j_prev != j)
                max_B = -1 # (j_prev == j)

                for j_prev in range(M): # cat[i-2]
                    prev_count = dp_prev[j_prev][j]
                    if prev_count == -1:
                        continue
                    
                    if j == j_prev:
                        if val_with_penalty >= K:
                            max_B = max(max_B, prev_count + 1)
                    else:
                        if val_no_penalty >= K:
                            max
0