<p>You are given a 2D <strong>binary</strong> array <code>grid</code>. You need to find 3 <strong>non-overlapping</strong> rectangles having <strong>non-zero</strong> areas with horizontal and vertical sides such that all the 1&#39;s in <code>grid</code> lie inside these rectangles.</p>

<p>Return the <strong>minimum</strong> possible sum of the area of these rectangles.</p>

<p><strong>Note</strong> that the rectangles are allowed to touch.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1],[1,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example0rect21.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 280px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(1, 0)</code> are covered by a rectangle of area 2.</li>
	<li>The 1&#39;s at <code>(0, 2)</code> and <code>(1, 2)</code> are covered by a rectangle of area 2.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,1,0],[0,1,0,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">5</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/14/example1rect2.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 356px; height: 198px;" /></p>

<ul>
	<li>The 1&#39;s at <code>(0, 0)</code> and <code>(0, 2)</code> are covered by a rectangle of area 3.</li>
	<li>The 1 at <code>(1, 1)</code> is covered by a rectangle of area 1.</li>
	<li>The 1 at <code>(1, 3)</code> is covered by a rectangle of area 1.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either 0 or 1.</li>
	<li>The input is generated such that there are at least three 1&#39;s in <code>grid</code>.</li>
</ul>

from sortedcontainers import SortedList
class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        #Preprocess:
        rows = [list(filter(row.__getitem__, range(n))) for row in grid]
        cols = [[] for _ in range(n)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    cols[j].append(i)
        #Sweepline from top, from left
        #Each line, try splitting each side
        #O(nlogn)
        def one(i1, j1, i2, j2):
            x1, y1, x2, y2 = i2, j2, i1, j1
            for k in range(i1, i2+1):
                l_idx = bisect_left(rows[k], j1)
                r_idx = bisect_right(rows[k], j2)-1
                if l_idx<=r_idx:
                    l, r = rows[k][l_idx], rows[k][r_idx]
                    x1 = min(x1, k)
                    y1 = min(y1, l)
                    x2 = k
                    y2 = max(y2, r)
            if x1<=x2 and y1<=y2:
                return (x2+1-x1)*(y2+1-y1)
            else:
                return 1
        #O(n^2logn)
        def two(i1, j1, i2, j2):
            msf = inf
            for k in range(i1, i2):
                msf = min(msf, one(i1, j1, k, j2)+one(k+1, j1, i2, j2))
            for k in range(j1, j2):
                msf = min(msf, one(i1, j1, i2, k)+one(i1, k+1, i2, j2))
            return msf
        #O(n^3logn)
        def three():
            msf = inf
            for k in range(m-1):
                msf = min(msf, one(0, 0, k, n-1)+two(k+1, 0, m-1, n-1))
                msf = min(msf, two(0, 0, k, n-1)+one(k+1, 0, m-1, n-1))
            for k in range(n-1):
                msf = min(msf, one(0, 0, m-1, k)+two(0, k+1, m-1, n-1))
                msf = min(msf, two(0, 0, m-1, k)+one(0, k+1, m-1, n-1))
            return msf
        return three()
932