Sparse Ones in a Grid

Hard

A grid is width × height, and every cell holds 0 or 1. Every square block of size side × side must contain at most limit ones. Return the largest number of ones the whole grid can contain.

Example 1

width=4, height=3, side=2, limit=1 → 4

Place ones where both coordinates are even: (0, 0), (0, 2), (2, 0), (2, 2). Every 2 × 2 square holds at most one of them, giving 4 ones.

Example 2

width=3, height=3, side=3, limit=9 → 9

The limit allows the whole 3 × 3 grid to be filled with ones.

Example 3

width=5, height=5, side=2, limit=0 → 0

Constraints

1 ≤ width, height ≤ 100
1 ≤ side ≤ min(width, height)
0 ≤ limit ≤ side²

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Math Sorting Heap (Priority Queue)

Similar problems

Prices That Fade With Each Sale Medium Same Prizes, Different Tastes Medium Equal Letters Kept Apart Hard Growing Capital Project by Project Hard Most Orders by Their Deadlines Hard

Input

width=4, height=3, side=2, limit=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.