Quiz Points With Rest Breaks

Medium

A quiz contestant goes through the tasks strictly in order. Task i is described by tasks[i] = [points, rest]: solving it earns points points, but the next rest tasks are burned and can no longer be solved. A task may also be skipped, in which case the contestant moves straight on to the next one. Return the maximum total score the contestant can earn.

Example 1

tasks=[[6, 1], [5, 1], [7, 2], [3, 1]] → 13

Solve task 0 (+6) and sit out task 1, then solve task 2 (+7), which burns task 3. That makes 13, and no plan does better.

Example 2

tasks=[[2, 5], [9, 1], [4, 1]] → 9

It pays to skip task 0 and take task 1 for 9 points (task 2 is then off-limits).

Example 3

tasks=[[4, 3]] → 4

Constraints

1 ≤ len(tasks) ≤ 10⁵
Each tasks[i] has exactly two numbers
1 ≤ points ≤ 10⁵
0 ≤ rest ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

tasks=[[6, 1], [5, 1], [7, 2], [3, 1]]

Expected

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