The Barista's Calm Streak

Medium

A coffee shop is open for n minutes. At the start of minute i, guests[i] guests walk in, and they all leave by the end of that minute. The barista is sometimes in a bad mood: moody[i] = 1 if they are in a bad mood during minute i, and 0 otherwise. Guests who arrive during a bad-mood minute leave unhappy; everyone else leaves pleased. Once per day the barista can pull themselves together and stay calm for streak consecutive minutes, during which every guest is pleased. Return the largest possible number of pleased guests over the day.

Example 1

guests=[4, 2, 0, 3, 5, 1], moody=[0, 1, 1, 0, 1, 1], streak=2 → 13

Without the trick, 4 + 3 = 7 guests are pleased. Staying calm during minutes 4 and 5 is best: 5 + 1 = 6 more guests. The total is 13.

Example 2

guests=[6, 6, 6], moody=[0, 0, 0], streak=3 → 18

The barista is calm all day anyway, so all 18 guests are pleased.

Example 3

guests=[10, 1, 1, 10], moody=[1, 0, 0, 1], streak=1 → 12

Constraints

1 ≤ streak ≤ n ≤ 2·10⁴
len(guests) = len(moody) = n
0 ≤ guests[i] ≤ 1000
moody[i] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Evenly Stepped Stretches Medium Longest Run of Ones With One Fix Medium Nearest k Values Medium Windows With a Small Product Medium

Input

guests=[4, 2, 0, 3, 5, 1], moody=[0, 1, 1, 0, 1, 1], streak=2

Expected

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