Observe that the productivity of the weekdays between two holiday is fixed.

Therefore, we can calculate the productivity \(P_i\) for each holidays on day \(a\) and \(b\) where \(i = |a-b|\) .We have \(P_{i+1}= a_1 + \cdots + a_{\lceil \frac{i}{2} \rceil}+ \cdots + a_1\) for odd \(i\) and \(P_{i+1} = a_1 + \cdots + a_{\lfloor \frac{i}{2} \rfloor} + a_{\lfloor \frac{i}{2} \rfloor} + \cdots + a_1\) for even \(i\).

This can be precalculated using loops or prefix sums in \(\mathcal{O}(n)\).

After calculating the productivity, the problem can be transformed into a infinite knapsack dp, where there are \(n\) items, and each item have an pair (weight, value) equals to \((i, P_i)\).

Let \(dp[i]\) be the maximum value such that the total weight is \(i\). As the sum of difference of the holidays is \(n\), the answer would be \( dp[n]\).

Let’s consider the first sample.

The productivity for each gap for the sample would be \(P_1 = 0, P_2= 10, P_3 = 20, P_4= 30, P_5= 40, P_6= 41, P_7= 42,\).

Then the maximum productivity would be \(P_2 + P_5= 50\).

Thus, the problem is solved in \(\mathcal O(n^2)\).

Solution Code