結果

問題 No.2473 Fraises dans une boîte
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-07-17 21:21:12
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,442 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 83,836 KB
最終ジャッジ日時 2024-04-24 23:24:11
合計ジャッジ時間 27,615 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,480 KB
testcase_01 AC 45 ms
54,016 KB
testcase_02 AC 72 ms
67,200 KB
testcase_03 AC 43 ms
52,480 KB
testcase_04 AC 46 ms
52,096 KB
testcase_05 AC 43 ms
52,736 KB
testcase_06 AC 822 ms
82,020 KB
testcase_07 AC 580 ms
82,404 KB
testcase_08 AC 838 ms
82,800 KB
testcase_09 AC 751 ms
82,520 KB
testcase_10 AC 743 ms
83,036 KB
testcase_11 AC 48 ms
53,632 KB
testcase_12 AC 47 ms
53,632 KB
testcase_13 AC 653 ms
83,836 KB
testcase_14 AC 671 ms
83,588 KB
testcase_15 AC 700 ms
83,420 KB
testcase_16 AC 627 ms
83,168 KB
testcase_17 AC 643 ms
82,816 KB
testcase_18 AC 720 ms
82,984 KB
testcase_19 AC 676 ms
82,740 KB
testcase_20 AC 669 ms
82,784 KB
testcase_21 AC 600 ms
82,504 KB
testcase_22 AC 632 ms
83,024 KB
testcase_23 AC 753 ms
83,132 KB
testcase_24 AC 759 ms
82,672 KB
testcase_25 AC 709 ms
82,592 KB
testcase_26 AC 721 ms
83,632 KB
testcase_27 AC 746 ms
83,148 KB
testcase_28 AC 754 ms
83,536 KB
testcase_29 AC 826 ms
83,312 KB
testcase_30 AC 608 ms
83,032 KB
testcase_31 AC 613 ms
83,064 KB
testcase_32 AC 841 ms
82,644 KB
testcase_33 AC 720 ms
83,308 KB
testcase_34 AC 642 ms
83,088 KB
testcase_35 AC 707 ms
83,024 KB
testcase_36 AC 794 ms
82,904 KB
testcase_37 AC 691 ms
83,012 KB
testcase_38 AC 615 ms
82,820 KB
testcase_39 AC 739 ms
83,036 KB
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 RE -
testcase_65 RE -
testcase_66 RE -
testcase_67 RE -
testcase_68 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

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

6乗ver

"""

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]

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

# ここからdp
for hsize in range(1,H+1): #縦のサイズが小さい領域から調べる

    for wsize in range(1,W+1): #横のサイズが小さい領域から調べる

        for x1 in range(H): #左上のx座標

            x2 = x1 + hsize
            if x2 > H:
                break
            
            for y1 in range(W): #左上のy座標

                y2 = y1 + wsize
                if y2 > W:
                    break

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

                now_ans = inf

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

                for tmpx in range(x1,x2):
                    nsum = 0
                    for tmpy in range(y1,y2):
                        nsum += S[tmpx][tmpy]
                    if nsum == 0:
                        pl = 1
                    else:
                        pl = 0
                    zerox.append(zerox[-1] + pl)

                for tmpy in range(y1,y2):
                    nsum = 0
                    for tmpx in range(x1,x2):
                        nsum += S[tmpx][tmpy]
                    if nsum == 0:
                        pl = 1
                    else:
                        pl = 0
                    zeroy.append(zeroy[-1] + pl)

                #print (zerox,zeroy)

                for xmid in range(x1,x2+1):

                    for ymid in range(y1,y2+1):

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

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

                        now_ans = min(now_ans , cost)
                        
                lis[x1][x2][y1][y2] = now_ans

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


print (lis[0][H][0][W])
0