A brute force solution suffices for this subtask.

Time Complexity: ~\mathcal{O}(NM^2)~

Let's say student ~i~ solves problem ~j~ with extra help, and problem ~j~ was their ~k^{th}~ unsolved problem, the amount of penalty they lose is:

$$\displaystyle kv_j+v_{j+1}+v_{j+2}+\dots+v_M$$

Previously, ~v_{j+1}+v_{j+2}+\dots+v_M~ was calculated manually in ~\mathcal{O}(M)~ time. Using a prefix sum array speeds this up to ~\mathcal{O}(1)~.

Time Complexity: ~\mathcal{O}(NM)~

Firstly, calculate the penalty for each student assuming that they don't ask for help. The penalty for a student who has solved ~i~ problems is:

$$\displaystyle v_{i+1}+2v_{i+2}+\dots+(M-i)v_M = \sum_{k=i+1}^M v_k + \sum_{k=i+2}^M v_k + \dots + \sum_{k=M}^M v_k$$

This can be calculated quickly using a prefix sum array (there are other ways to do this as well).

Now, we just have to find the maximum penalty loss a student can obtain.

Consider problem #~i~:

Let ~m=v_i~

Let ~b=v_{i+1}+v_{i+2}+\dots+v_M~

A student who solves problem ~i~ when it's their ~x^{th}~ unsolved problem loses ~mx+b~ penalty. Notice how this is the same as getting the y-coordinate of a line at a given x-coordinate. Thus, we now convert each problem into a line ~y=mx+b~.

Additionally, if we loop through the students from most problems solved to least problems solved, problems become available for extra help in the order of highest index to lowest index (and don't ever become unavailable). Thus, we can simply insert problems into a data structure when they become available, and query for the maximal value at a certain ~x~-value to compute the answer for a student.

The only issue left is that for each student, we query ~x=1~ for their first unsolved problem, ~x=2~ for their second, etc. To fix this, we simply shift the ~x^{th}~ line ~i~ units to the left for all ~1 \le i \le M~ so that we only query ~1~ ~x~-value per student. This works because the set of unsolved problems for each student occupies a continuous range of indices.

A data structure that maintains this set of available lines efficiently is the Dynamic Convex Hull Trick.

Time Complexity: ~\mathcal{O}((N+M) \log M + N \log N)~

We can expand on our solution from subtask 3 to account for the availability of help on certain days.

We can do this with a segment tree: ~seg[l \dots r]~ maintains a Dynamic CHT for all the problems that are available in the days ~[l, r]~. When inserting problem ~i~, stop when ~seg[l \dots r]~ is completely within ~[l_i, r_i]~ and insert the problem into ~seg[l \dots r]~.

When querying for student ~i~, we query every ~seg[l \dots r]~ where ~l \le d_i \le r~. There are ~\le \log D~ such ranges and they also cover the set of all problems available to that student.

This can also be done using divide and conquer: solve(l, r) considers only the problems and students available in the days ~[l, r]~. Then, relevant students and problems are passed onto solve(l, mid) and solve(mid + 1, r) respectively, where ~mid= \left\lfloor \frac{l+r}{2} \right\rfloor~. Calling solve(1, D) will compute the answer for each student and we can simply print it out afterwards.

Time Complexity: ~\mathcal{O}((N+M)\log M \log D + N \log N)~

There is also a solution with complexity ~\mathcal{O}(M \sqrt{M} + N \log M \sqrt{M})~ that does a linesweep on the days. In order to delete lines from the CHT, they're stored in blocks of size ~\sqrt{M}~ and the CHT is rebuilt each time. However, that solution won't be gone over in full detail here.

As always, feedback is welcome.