Problem Link
[Contest][1]Author: Sahil Rajput
Tester: Sahil Rajput
Editorialist: Sahil Rajput
Difficulty
HardPrerequisites
Maths, Dynamic Programming, Segment Tree, Sparse Table, Moving WindowExplanation
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).