1533. How Many Windows Clear the Bar

An R by C grid is given together with a window height h, a window width w and a threshold t. Count the h by w windows lying entirely inside the grid whose values add up to t OR MORE. Print that count.

1 2 3 4 h = 2, w = 2, t = 20 5 6 7 8 -> 4 9 10 11 12

The six windows total 14, 18, 22, 30, 34, 38, and four of them reach 20.

1 2 3 4 h = 2, w = 2, t = 1000 -> 0 nothing reaches it 5 6 7 8 9 10 11 12

1 2 3 4 h = 2, w = 2, t = -1000 -> 6 everything does 5 6 7 8 9 10 11 12

## What most people try first

Summing each window. The position count is (R-h+1)(C-w+1) and each sum costs h w, so at R = C = 1000 with h = w = 500 that is about 6 * 10^10 additions.

The second reflex, once the corner-total table is in hand, is to compare the AVERAGE against something, or to divide. Nothing here needs division: the threshold is on the total, so the comparison is an integer one.

## One table, then one comparison per position

build P as in problem 729 count = 0 for every top-left (i, j) with i + h - 1 <= R and j + w - 1 <= C: if rectangle total at (i, j, i+h-1, j+w-1) >= t: count++

## Why the four lookups are correct, and why the comparison is not strict

The four-term expression is exact because the strip above and the strip to the left between them cover the block above-and-left twice, and adding it back once leaves precisely the window. Nothing is approximated, so the comparison that follows can never be off by a rounding.

The statement says t OR MORE, so a window totalling exactly t always counts. The declared test whose bar is 14, met exactly by one window, differs by one between >= and >. That one test is the whole difference, which is why an implementation with the wrong comparison passes every other case.

## How large the answer can be

There are at most (R-h+1)(C-w+1) positions, so at most 10^6. The count itself fits comfortably in a signed 32 bit integer, whose limit is 2147483647. It is the TOTALS that do not.

## Overflow

A window of 10^6 cells at 10^9 reaches 10^15, and t is allowed to be as large as 10^15 too, so the table, the window total and the threshold all need 64 bits. Reading t into a 32 bit variable is the first thing to go wrong, before any arithmetic happens.

## The relationship with problem 1532

That problem finds the single heaviest window and its position; this one counts how many clear a bar. Same table, same four terms, different reduction over the same set of positions: a maximum there, a count here. Problem 730 uses the same table again with a window whose shape depends on the CELL rather than being fixed.

## Cost

O(R C) to build the table and O(R C) to scan, with O(R C) memory.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `1 ≤ h ≤ R` - `1 ≤ w ≤ C` - `-10^15 ≤ t ≤ 10^15` - `-10^9 ≤ each value ≤ 10^9` - `R` and `C` are independent, and so are `h` and `w`