結果

問題 No.3368 トッピング
コンテスト
ユーザー iro_
提出日時 2025-10-29 18:57:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,224 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 81,224 KB
最終ジャッジ日時 2025-11-17 20:40:57
合計ジャッジ時間 6,949 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline

    N, M, C, X = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    # 判定関数：この t 以上の最小満足度を実現できるか？
    def feasible(t):
        # nonpen[i][j] = A[i][j] >= t
        # pen[i][j] = A[i][j] >= t + C
        nonpen = [[a >= t for a in row] for row in A]
        pen = [[a >= t + C for a in row] for row in A]

        # 各 (i, j) について、そこから連続して pen が成立する最大長を求める
        maxlen = [[0]*M for _ in range(N)]
        for j in range(M):
            cnt = 0
            for i in range(N-1, -1, -1):
                if pen[i][j]:
                    cnt += 1
                else:
                    cnt = 0
                maxlen[i][j] = cnt

        # dp[i][p] = 位置 i からスタートし、ペナルティ発生位置を p 箇所確保できるか
        # i: 現在位置, p: 確保済みペナルティ数
        # 実際には幅優先的に探索（メモ化DFSでもOK）
        from collections import deque
        cap = X
        dp = [ [False]*(cap+1) for _ in range(N+2) ]
        dp[1][0] = True

        for i in range(1, N+1):
            for p in range(cap+1):
                if not dp[i][p]:
                    continue

                # 長さ1ブロック（非ペナルティ）
                if any(nonpen[i-1]):
                    dp[i+1][p] = True

                # 長さ≥2ブロック（ペナルティ）
                for j in range(M):
                    Lmax = maxlen[i-1][j]
                    if Lmax >= 2:
                        for L in range(2, Lmax+1):
                            ni = i + L
                            if ni > N+1:
                                break
                            np = min(cap, p + L)
                            dp[ni][np] = True

        return dp[N+1][cap]

    # 二分探索
    low = -10**9
    high = 10**9
    while low < high:
        mid = (low + high + 1) // 2
        if feasible(mid):
            low = mid
        else:
            high = mid - 1

    print(low)


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