Quiet and Sociable Tenants

Hard

A housing block is a grid of rows × cols flats. There are quiet quiet tenants and sociable sociable ones. Each tenant you move in needs a flat of their own; you do not have to house everyone. Neighbours are tenants in the flats directly above, below, left or right. A tenant's mood is: - quiet: starts at 120 and loses 30 for each neighbour (of either kind); - sociable: starts at 40 and gains 20 for each neighbour (of either kind). The block's mood is the sum of the moods of everyone housed. Return the largest possible mood of the block.

Example 1

rows=1, cols=3, quiet=2, sociable=1 → 260

Quiet tenants at both ends (120 − 30 = 90 each) and the sociable one in the middle (40 + 2·20 = 80): 90 + 80 + 90 = 260.

Example 2

rows=2, cols=2, quiet=0, sociable=3 → 200

Three sociable tenants in an L shape: the corner one has two neighbours (80), the other two have one each (60 + 60), 200 in total.

Example 3

rows=3, cols=3, quiet=2, sociable=0 → 240

Place the two quiet tenants apart so they are not neighbours: 120 + 120 = 240.

Constraints

1 ≤ rows, cols ≤ 5
0 ≤ quiet, sociable ≤ min(rows · cols, 6)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Memoization Dynamic Programming Bitmask

Similar problems

Fresh Trays for Every Party Hard Shared Pool Race to a Goal Medium Cheapest Basket with Bundles Medium Groups With Equal Sums Medium Settle Up in the Fewest Transfers Hard

Input

rows=1, cols=3, quiet=2, sociable=1

Expected

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