tourist vs rainboy

For tourist, the time $A_i$ spent on problem $i$ is included in the completion times of problems $i,i+1,\cdots,N$. Therefore, tourist's penalty is

$$\sum_{i=1}^{N}(N-i+1)A_i.$$

For rainboy, $A_i$ is included in the completion times of problems $1,2,\cdots,i$, so rainboy's penalty is

$$\sum_{i=1}^{N}iA_i.$$

Thus, the required difference is

$$\sum_{i=1}^{N}(2i-N-1)A_i.$$

It can be computed in one pass over the array. The time complexity is $O(N)$.

Solution written by GPT5.6