### Problem Link

[Contest][1]**Author:** Sahil Rajput

**Tester:** Sahil Rajput

**Editorialist:** Sahil Rajput

### Difficulty

Hard### Prerequisites

Maths, Dynamic Programming, Segment Tree, Sparse Table, Moving Window### Explanation

You can tackle this question with multiple approaches, one is simple DP algorithm, make an array dp[i][j] which will store the maximum happiness value that you can gain when you're on poisition j at i th launching.You can calculate value by this formula:

**dp[i][j] = max [k = - t * d…t * d] (dp[i — 1][j + k] + b[i] — |a[i] — j|) where t = t[i] — t[i — 1]**.

If you look up for all k, since the table’s size is O(mn), the overall complexity will be O(mn^2). You can also use segment tree or sparse table but the original and intended solution uses sliding window maximum since the interval** [j — t * d, j + t * d] **is independent for all the fireworks. It can be implemented by simple array or deque. This will speed up to calculate formula, and overall complexity will be O(mn).