結果

問題 No.2473 Fraises dans une boîte
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-08-07 04:14:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,592 ms / 4,000 ms
コード長 3,462 bytes
コンパイル時間 446 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 81,668 KB
最終ジャッジ日時 2024-04-24 23:27:34
合計ジャッジ時間 45,918 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
52,736 KB
testcase_01 AC 43 ms
52,992 KB
testcase_02 AC 45 ms
52,992 KB
testcase_03 AC 44 ms
52,736 KB
testcase_04 AC 44 ms
52,608 KB
testcase_05 AC 45 ms
52,608 KB
testcase_06 AC 45 ms
53,120 KB
testcase_07 AC 103 ms
76,672 KB
testcase_08 AC 63 ms
63,616 KB
testcase_09 AC 114 ms
76,480 KB
testcase_10 AC 109 ms
76,672 KB
testcase_11 AC 44 ms
52,608 KB
testcase_12 AC 44 ms
52,608 KB
testcase_13 AC 103 ms
76,544 KB
testcase_14 AC 104 ms
76,544 KB
testcase_15 AC 103 ms
76,672 KB
testcase_16 AC 103 ms
76,672 KB
testcase_17 AC 105 ms
76,544 KB
testcase_18 AC 107 ms
76,544 KB
testcase_19 AC 99 ms
76,800 KB
testcase_20 AC 103 ms
76,544 KB
testcase_21 AC 102 ms
76,672 KB
testcase_22 AC 106 ms
76,612 KB
testcase_23 AC 101 ms
76,416 KB
testcase_24 AC 93 ms
75,008 KB
testcase_25 AC 105 ms
76,416 KB
testcase_26 AC 104 ms
76,288 KB
testcase_27 AC 110 ms
76,572 KB
testcase_28 AC 101 ms
76,032 KB
testcase_29 AC 93 ms
74,112 KB
testcase_30 AC 114 ms
76,552 KB
testcase_31 AC 107 ms
76,544 KB
testcase_32 AC 83 ms
72,192 KB
testcase_33 AC 109 ms
76,352 KB
testcase_34 AC 107 ms
76,956 KB
testcase_35 AC 105 ms
76,240 KB
testcase_36 AC 90 ms
75,008 KB
testcase_37 AC 103 ms
76,416 KB
testcase_38 AC 115 ms
77,020 KB
testcase_39 AC 92 ms
74,880 KB
testcase_40 AC 228 ms
78,292 KB
testcase_41 AC 231 ms
78,488 KB
testcase_42 AC 109 ms
77,192 KB
testcase_43 AC 710 ms
78,848 KB
testcase_44 AC 719 ms
79,308 KB
testcase_45 AC 238 ms
78,720 KB
testcase_46 AC 1,316 ms
80,812 KB
testcase_47 AC 1,379 ms
79,976 KB
testcase_48 AC 1,354 ms
80,384 KB
testcase_49 AC 2,317 ms
81,212 KB
testcase_50 AC 1,004 ms
80,772 KB
testcase_51 AC 2,371 ms
81,428 KB
testcase_52 AC 2,327 ms
81,340 KB
testcase_53 AC 2,453 ms
80,996 KB
testcase_54 AC 1,939 ms
81,020 KB
testcase_55 AC 2,497 ms
81,668 KB
testcase_56 AC 1,130 ms
80,768 KB
testcase_57 AC 2,013 ms
80,920 KB
testcase_58 AC 717 ms
80,156 KB
testcase_59 AC 685 ms
80,112 KB
testcase_60 AC 2,431 ms
81,276 KB
testcase_61 AC 1,709 ms
81,080 KB
testcase_62 AC 2,123 ms
81,016 KB
testcase_63 AC 1,123 ms
81,068 KB
testcase_64 AC 942 ms
80,384 KB
testcase_65 AC 2,592 ms
81,440 KB
testcase_66 AC 808 ms
80,244 KB
testcase_67 AC 94 ms
77,952 KB
testcase_68 AC 2,151 ms
80,868 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

Fraises dans une boîte(6)
想定解

3乗計算量Ver

色々と整っていないので、あまりに読み辛いです
rinさんのを読んでください…

"""

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 = [[inf] * (W+1) for i in range(H+1)]
for j in range(W+1):
    lis[H][j] = 0
for i in range(H+1):
    lis[i][W] = 0

# ここからdp

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

        if SSum[H][W] - SSum[x1][W] - SSum[H][y1] + SSum[x1][y1] <= 1:
            lis[x1][y1] = 0
            continue

        # ここから、最小値の導出処理
        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) )
        
        for xmid in range(H,x1-1,-1):

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

            for ymid in ymids:

                assert x1 <= xmid <= H
                assert y1 <= ymid <= W
                
                #右下が0で無い場合、駄目
                if SSum[H][W] - SSum[xmid][W] - SSum[H][ymid] + SSum[xmid][ymid] != 0:
                    continue
                #左上・右下共に0の場合は推移の意味が無いのでダメ
                if (xmid-x1) * (ymid-y1) == 0 and (H-xmid) * (W-ymid) == 0:
                    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,lu1)

                if xmid == x1 and ymid == y1:
                    continue
                now_ans = min(now_ans , cost)

          
        lis[x1][y1] = now_ans

print (lis[0][0])
0