結果

問題 No.2473 Fraises dans une boîte
ユーザー 👑 SPD_9X2
提出日時 2023-08-07 03:30:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,259 bytes
コンパイル時間 492 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 82,292 KB
最終ジャッジ日時 2024-11-07 08:43:33
合計ジャッジ時間 46,606 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14 WA * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

Fraises dans une boîte(6)
注: すごくバグってます

"""

import sys
from sys import stdin

H,W = map(int,stdin.readline().split())

S = [list(map(int,stdin.readline().split())) for i in range(H)]

# 制約チェック
#assert 1 <= H <= 22
#assert 1 <= W <= 22
assert len(S) == H
for s in S:
    assert len(s) == W
    for i in s:
        assert i == 0 or i == 1

# 領域の和を高速に導出するための2次元累積和
SSum = [[0] * (W+1) for i in range(H+1)]
for i in range(H):
    for j in range(W):
        SSum[i+1][j+1] += S[i][j]
for i in range(H):
    for j in range(W+1):
        SSum[i+1][j] += SSum[i][j]
for i in range(H+1):
    for j in range(W):
        SSum[i][j+1] += SSum[i][j]

# 同じ行で、i番目からみて直左にあるjのインデックスを記録
SR = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == 1:
            SR[i][j] = j
for i in range(H):
    for j in range(W-1):
        SR[i][j+1] = max(SR[i][j+1] , SR[i][j])

# メモ化用の2次元list
inf = float("inf")
lis = [[0] * (W+1) for i in range(H+1)]

# ここからdp

for x1 in range(H-1,-1,-1): #左上のx座標
    for y1 in range(W-1,-1,-1): #左上のy座標

        # ここから、最小値の導出処理
        now_ans = inf

        # 左上領域の空行カウント用の配列
        zerox = [0]
        zeroy = [0]

        for tmpx in range(x1,H):
            nsum = SSum[tmpx+1][W] - SSum[tmpx][W] - SSum[tmpx+1][y1] + SSum[tmpx][y1]
            zerox.append(zerox[-1] + (min(1,nsum)^1) )

        for tmpy in range(y1,W):
            nsum = SSum[H][tmpy+1] - SSum[H][tmpy] - SSum[x1][tmpy+1] + SSum[x1][tmpy]
            zeroy.append(zeroy[-1] + (min(1,nsum)^1) )

        #print (x1,y1,zerox,zeroy)
        if zerox[-1] == len(zerox)-1:
            now_ans = 0

        #for xmid in range(x1,H+1):

        ymid = y1
        for xmid in range(H,x1-1,-1):

            # ymidは一意に決まる
            if xmid == H:
                ymid = W
            elif xmid == H-1:
                ymid = max(y1,SR[xmid][-1]+1)
            else:
                ymid = max(ymid , SR[xmid][-1]+1)

            #print (x1,y1,xmid,ymid)
            
            #右下が0で無い場合、駄目
            if SSum[H][W] - SSum[xmid][W] - SSum[H][ymid] + SSum[xmid][ymid] != 0:
                #print (x1,y1,xmid,ymid,"can't because nonzero 右下")
                continue
            #左上・右下共に0の場合は推移の意味が無いのでダメ
            if (xmid-x1) * (ymid-y1) == 0 and (H-xmid) * (W-ymid) == 0:
                #print (x1,y1,xmid,ymid,"意味がない")
                continue

            cost = 0

            # 左上区間の1の個数
            lu1 = SSum[xmid][ymid] - SSum[xmid][y1] - SSum[x1][ymid] + SSum[x1][y1]
            cost += (xmid-x1-zerox[xmid-x1]) * (ymid-y1-zeroy[ymid-y1]) - lu1

            # 左下と右上
            cost += lis[xmid][y1] + lis[x1][ymid]

            # デバッグ用
            #print (x1,y1,xmid,ymid,"cost",cost)

            now_ans = min(now_ans , cost)

          
        lis[x1][y1] = now_ans

        # デバッグ用
        #print (x1,x2,y1,y2,now_ans)

#print (lis)
print (lis[0][0])
0