Stamina and Tasks

Key Observation

The annoying part is stamina being a real number. But here is the trick: the problem is perfectly linear in stamina.

Suppose before some suffix of tasks your stamina is $S$. Every score you can earn in that suffix is multiplied by $S$, and every later stamina value is also multiplied by $S$. So if the best answer for that suffix starting with stamina $1$ is $dp[i]$, then starting with stamina $S$ gives exactly:

$$S \cdot dp[i]$$

No need to store possible stamina values. That would be overkill, and overkill is where wrong solutions go to die.

Backward DP

Let $dp[i]$ be the maximum score obtainable from tasks $i, i+1, \dots, n$ assuming current stamina is $1$ right before task $i$.

For task $i$, define:

$$q_i = 1 - \frac{p_i}{100}$$

There are two choices:

• Skip task $i$: value is $dp[i+1]$.
• Complete task $i$: gain $c_i$ now, then stamina becomes $q_i$, so the suffix contributes $q_i \cdot dp[i+1]$.

Therefore:

$$dp[i] = \max\left(dp[i+1],\ c_i + q_i \cdot dp[i+1]\right)$$

The base case is:

$$dp[n+1] = 0$$

We only need the next value, so one variable is enough.

Why This Is Correct

The recurrence checks both legal actions at task $i$. If we skip, the state of the suffix is unchanged. If we complete, the immediate gain is $c_i$ because current stamina is $1$, and by linearity the optimal suffix value becomes $q_i \cdot dp[i+1]$.

Since every optimal strategy must either skip or complete task $i$, the maximum of these two values is exactly optimal. Processing from right to left computes all suffix answers in valid dependency order.

Complexity

Each task is processed once.

$$O(n)$$

per test case, and

$$O(1)$$

extra memory besides the input arrays. With $\sum n \le 10^5$, this is comfortably fast.