結果

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

ソースコード

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
while (ng - ok) > 1:
    mid = (ok + ng) // 2
    # mid = 40
    # ok = 999999
    # ng = -999999
    dp = [[-(N + 1), -(N + 1)] for _ in range(M)] 
    # dp[j][k]:= 直前の食材カテゴリがjで、(k=0の時、直前と一緒なので既に+1やってる)の時のmaxペナルティ数
    for i in range(N):
        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 = [-2, -2]
            second = [-2, -2]
            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]
            for j in range(M):
                if(min(A[i - 1][j], A[i][j]) - C >= mid):
                    if(first[1] == dp[j][1]):
                        ndp[j][0] = max(ndp[j][0], dp[j][0] + 1, second[1] + 2)
                    else:
                        ndp[j][0] = max(ndp[j][0], dp[j][0] + 1, first[1] + 2)
                if(A[i][j] >= mid):
                    max_v = -2
                    if(first[0] == dp[j]):
                        max_v = max(max_v, second[0])
                    else:
                        max_v = max(max_v, first[0])
                    if(first[1] == dp[j]):
                        max_v = max(max_v, second[1])
                    else:
                        max_v = max(max_v, first[1])
                    ndp[j][1] = max(ndp[j][1], max_v)
            dp = ndp[:]
    # print(mid, dp)
    if(max([max(l) for l in dp]) >= X):
        ok = mid
    else:
        ng = mid
print(ok)
0