結果

問題 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
コンパイル時間 254 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 83,732 KB
最終ジャッジ日時 2024-11-07 08:40:50
合計ジャッジ時間 25,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,864 KB
testcase_01 AC 42 ms
53,888 KB
testcase_02 AC 59 ms
67,328 KB
testcase_03 AC 39 ms
52,736 KB
testcase_04 AC 39 ms
52,480 KB
testcase_05 AC 40 ms
52,608 KB
testcase_06 AC 729 ms
82,100 KB
testcase_07 AC 544 ms
82,276 KB
testcase_08 AC 798 ms
82,624 KB
testcase_09 AC 707 ms
82,568 KB
testcase_10 AC 678 ms
82,844 KB
testcase_11 AC 43 ms
53,760 KB
testcase_12 AC 45 ms
54,144 KB
testcase_13 AC 588 ms
83,420 KB
testcase_14 AC 627 ms
83,716 KB
testcase_15 AC 638 ms
82,732 KB
testcase_16 AC 583 ms
82,824 KB
testcase_17 AC 596 ms
82,632 KB
testcase_18 AC 624 ms
82,852 KB
testcase_19 AC 622 ms
82,424 KB
testcase_20 AC 624 ms
82,592 KB
testcase_21 AC 532 ms
82,564 KB
testcase_22 AC 594 ms
83,096 KB
testcase_23 AC 701 ms
82,940 KB
testcase_24 AC 690 ms
82,548 KB
testcase_25 AC 675 ms
82,592 KB
testcase_26 AC 676 ms
83,552 KB
testcase_27 AC 687 ms
82,972 KB
testcase_28 AC 714 ms
83,732 KB
testcase_29 AC 771 ms
82,880 KB
testcase_30 AC 553 ms
82,588 KB
testcase_31 AC 561 ms
82,756 KB
testcase_32 AC 770 ms
82,824 KB
testcase_33 AC 652 ms
82,856 KB
testcase_34 AC 579 ms
82,388 KB
testcase_35 AC 652 ms
82,764 KB
testcase_36 AC 727 ms
82,720 KB
testcase_37 AC 630 ms
82,444 KB
testcase_38 AC 558 ms
82,936 KB
testcase_39 AC 679 ms
83,228 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