結果

問題 No.3368 トッピング
コンテスト
ユーザー Koi
提出日時 2025-11-16 17:18:20
言語 PyPy3
(7.3.15)
結果
OLE  
実行時間 -
コード長 1,886 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 148,020 KB
最終ジャッジ日時 2025-11-17 20:48:37
合計ジャッジ時間 7,079 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other OLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

ok = -10 ** 9
ng = 10 ** 9 + 1

def solve(mid):
    dp = [[-(N + 1), -(N + 1)] for _ in range(M)] 
    # dp[j][k]:= 直前の食材カテゴリがjで、(k=0の時、直前と一緒なので既に+1やってる)の時のmaxペナルティ数
    for i in range(N):
        # print(i, dp)
        if(i == 0):
            for j in range(M):
                if(A[i][j] >= mid):
                    dp[j][1] = 0
        else:
            ndp = [[-(N + 1), -(N + 1)] for _ in range(M)] 
            first = [-(N + 1), -(N + 1)]
            second = [-(N + 1), -(N + 1)]

            for j in range(M):
                for k in range(2):
                    if(dp[j][k] >= first[k]):
                        second[k] = first[k]
                        first[k] = dp[j][k]
                    elif(dp[j][k] >= second[k]):
                        second[k] = dp[j][k]
            # print(first, second)
            for j in range(M):
                if(min(A[i - 1][j], A[i][j]) - C >= mid):
                    ndp[j][0] = max(ndp[j][0], dp[j][0] + 1, dp[j][1] + 2)
                if(A[i][j] >= mid):
                    max_v = -(N + 1)
                    if(first[0] == dp[j][0]):
                        max_v = max(max_v, second[0])
                    else:
                        max_v = max(max_v, first[0])
                    if(first[1] == dp[j][1]):
                        max_v = max(max_v, second[1])
                    else:
                        max_v = max(max_v, first[1])
                    print(i, j, max_v)
                    ndp[j][1] = max(ndp[j][1], max_v)
            dp = ndp[:]
    # print(mid, dp)
    return max([max(l) for l in dp])
while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if(solve(mid) >= X):
        ok = mid
    else:
        ng = mid
print(ok)
0