1534. The Biggest Square Under a Cap

An R by C grid of NON-NEGATIVE values is given together with a cap c. Find the largest side length s such that some s by s square lying entirely inside the grid has a total of at most c. Print that side length, or 0 if even a single cell is already above the cap.

1 2 3 4 c = 12 -> 1 5 6 7 8 a 2 by 2 square totals at least 14, and cell 1 is under 12 9 10 11 12

0 0 0 0 c = 1 -> 3 0 0 0 0 a 3 by 3 of zeros fits; a 4 by 4 does not exist here, 0 0 0 9 because the grid is only 3 rows tall

1 1 1 1 c = 9 -> 3 1 1 1 1 a 3 by 3 totals 9 exactly, a 4 by 4 totals 16 1 1 1 1 1 1 1 1

## What most people try first

Trying every side length from 1 upward and every position for each. There are min(R, C) side lengths and up to R C positions each, and with the corner-total table each test is constant, so it is O(R C min(R, C)): about 10^9 at the limits. Without the table it is far worse.

The other instinct is to grow a square greedily from the best single cell. That is wrong: the cheapest 1 by 1 need not sit inside the cheapest 2 by 2. In the second example above the cheapest cell is any zero, and the largest clean square is bounded by the SHORTER SIDE of the grid rather than by anything about that cell.

## The predicate is monotone, but only because the values are non-negative

Say a side length s is FEASIBLE when some s by s square totals at most c. If s is feasible then s - 1 is too: any s-1 by s-1 square inside the feasible one has a total no larger, because every cell dropped was at least zero. So feasibility is true up to some point and false after it, and the answer is the largest true one, found by binary search over 1 .. min(R, C).

With a negative value anywhere this collapses: a 3 by 3 square could total less than every 2 by 2 inside it, and the predicate would flicker. That is why the constraint says non-negative, and it is the load-bearing part of the statement rather than a convenience.

## The search

build P, the corner-total table of problem 729 lo = 1, hi = min(R, C), best = 0 while lo <= hi: mid = (lo + hi) / 2 if some mid by mid square totals <= c: best = mid; lo = mid + 1 else: hi = mid - 1 print best

The feasibility test scans every top-left position for one mid, which is O(R C), so the whole search is O(R C log min(R, C)), about 10^7 at the limits.

## Why the answer can be zero

best starts at 0 and stays there when even s = 1 fails, which happens exactly when every single cell is above c. Initialising best to 1 is the usual mistake and it is invisible on any grid containing a small value.

## The upper bound is min(R, C), not max

A square of side s needs s rows AND s columns. On a 3 by 4 grid the largest possible side is 3. Searching up to max(R, C) reads outside the grid in the feasibility test unless the position loops are also guarded, and then it simply wastes iterations.

## Overflow

A square can hold 10^6 cells of up to 10^9 each, so a total reaches 10^15, and c may itself be 10^15. Both are far past the 2147483647 a signed 32 bit integer holds, so the table, the totals and the cap are all 64 bit.

## Cost

O(R C log min(R, C)) time and O(R C) memory.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `0 ≤ c ≤ 10^15` - `0 ≤ each value ≤ 10^9`, so no value is negative - `R` and `C` are independent; the grid need not be square