### PROBLEM LINK

**Author:** Dmytro Berezin

**Tester:** Alexey Zayakin

**Editorialist:** Jakub Safin

### DIFFICULTY

EASY-MEDIUM

### PREREQUISITIES

dynamic programming

### PROBLEM

You’re given N arrays A_1,\dots,A_N; the i-th array has length M_i. You’re allowed to cyclically shift any array; you may perform this operation any number of times. Compute the maximum possible value of \sum_{i=1}^{N-1} i\left|A_i\lbrack M_i\rbrack-A_{i+1}\lbrack 1\rbrack\right| after performing zero or more cyclic shifts.

### QUICK EXPLANATION

Dynamic programming computing the maximum partial sums \sum_{j=2}^i (j-1)\left|A_{j-1}\lbrack M_{j-1}\rbrack -A_j\lbrack 1\rbrack\right| for each possible A_i\lbrack 1\rbrack (each cyclic shift of each array A_i).

### EXPLANATION

Let’s imagine we knew the optimal cyclic shift of the array A_i. The central observation is that the optimal cyclic shifts of the previous i-1 arrays and the next N-i arrays are independent - of course, they both depend on A_i\lbrack 1\rbrack and A_i\lbrack M_i\rbrack, but not on each other.

That means we can compute the maximum sum from arrays A_{1..i} for each possible cyclic shift of A_i - if we shifted A_i from the input by s_i, so that A_i\lbrack s_i+1\rbrack becomes A_i\lbrack 1\rbrack, let’s call that maximum possible sum S_{i,s_i} - and use dynamic programming to compute all S_{i,j} from the known values of S_{i-1,j}.

The initial condition is naturally S_{1,j}=0~\forall j, since there are 0 terms in that sum. For i > 1, assume we’ve computed all values S_{i-1,j}; we can write a general expression using these values and the input arrays:

where we’re using the fact that if the array A_{i-1} was shifted by j=s_{i-1}, then A_{i-1}\lbrack s_{i-1}+1\rbrack becomes its first element, so A_{i-1}\lbrack s_{i-1}\rbrack becomes its last element (we’re also using the convention A_{i-1}\lbrack 0\rbrack=A_{i-1}\lbrack M_{i-1}\rbrack).

Usually, working with absolute values directly is complicated. It’s a good idea to split the \mathrm{max}() into 2 cases based on which of the numbers A_i\lbrack s_i+1\rbrack, A_{i-1}\lbrack j\rbrack is greater, compute the separate maxima and take their maximum, but there’s a trick we can use here: |x|=\mathrm{max}(x,-x), so

In other words, we can compute the maxima for both possible signs and just take their maximum afterwards - the wrong sign will always give a \le number than the right one, so it won’t affect the result.

This trick is fairly common when you’re asked to compute the maximum of a function involving absolute values, e.g. in a grid with Manhattan distances, and simplifies the code considerably. Note that it fails if you need to compute a minimum instead.

Now let’s get back to our problem. It’s not very hard to compute the maxima we need now, since we can write

the term with the maximum doesn’t depend on s_i or A_i and since we already know all S_{i-1,j}, we can compute it in O(M_{i-1}) time and call it m_1. Similarly, we get

where the first term with the maximum can be computed just as easily; let’s call it m_2. The final formula is

If we use it, we can compute S_{i,s_i} for all 0 \le s_i < M_i in O(M_i) time.

This way, we can compute all the sums S_{i,j} for increasing i; to get the answer to the problem, we need to take \mathrm{max} (S_{N,j}) over all 0 \le j < M_N.

For a test case with \sum M_i = N, this algorithm then runs in O(N) time and O(N) memory.