For the first subtask, we can loop through all possible ways to split the array into at most ~M~ subarrays to assign to the groups. We can retrieve the sum of the pages for each subarray with a prefix sum array in ~\mathcal{O}(1)~.

Let ~sum_i~ be the sum of the ~i^{th}~ subarray. We can prove that it is always optimal to assign the largest ~sum_i~ to the group with the largest ~g_i~, the second largest ~sum_i~ to the group with the second largest ~g_i~, etc. After testing all possible ways to split the array into at most ~M~ subarrays, we can output the best answer.

Time Complexity: ~\mathcal{O}(N^{M-1})~

For the second subtask, we can perform dynamic programming. Let ~dp[i][j]~ represent the best answer with the first ~i~ chapters and ~j~ groups. The transition is trivial, and is left as an exercise for the reader (Hint: try all possible subarrays for the current group, including the empty subarray). The answer should be in ~dp[N][M]~.

Note that this dynamic programming algorithm only considers the groups in a specific order. However, in the actual problem, the groups are unordered. Thus we need to test all permutations of the group, and run dynamic programming on each permutation. Also note that some optimizations should be utilized that are described in the first subtask. For example, you should use a prefix sum array instead of looping.

Time Complexity: ~\mathcal{O}(M! \cdot M \cdot N^2)~

For the third subtask, we can binary search for the answer. Let ~mid~ be the current ~\max s_j~ that is tested to see whether it is possible to split the novel into up to ~M~ groups. We can greedily assign a subarray of chapters by looping until the last index which would allow ~s_1 \le mid~. We can do the same for ~s_j~ for all ~1 \le j \le M~. If the entire array can be assigned, then ~mid~ is valid. Otherwise ~mid~ is invalid.

If ~mid~ is valid, we must then test a lower ~mid~ (we overshot). Otherwise, we undershot, and we must test a higher ~mid~. We must find the location where ~mid~ is invalid, and ~mid+1~ is valid. ~mid+1~ is then the answer.

Note that we run into the same problem as subtask two, and all permutations of the groups must be tested.

Time Complexity: ~\mathcal{O}(M! \cdot M \cdot N \cdot \log K)~ where ~K~ is maximum possible answer ~(K = \sum_{i=1}^N p_i)~.

For the fourth subtask, we can use the same algorithm as subtask three. However, notice that instead of looping to find the subarray to assign to group ~j~, we can binary search (again) for the maximum length subarray to assign to group ~i~. Everything else is the same as subtask three.

Time Complexity: ~\mathcal{O}(M! \cdot M \cdot \log N \cdot \log K)~ where ~K~ is maximum possible answer ~(K = \sum_{i=1}^N p_i)~.

Note: For those that are TLEing but implementing the correct algorithm, it may help to know that division is extremely slow (around 10x slower than multiplication!), so always multiply instead of divide.

Note 2: There is an observation that could be made to reduce the ~M!~ to ~2^M~ in the time complexity, but it is not needed for this problem.