prefix sum и sliding window (Road Reform)

[zerone]

Доброго времени суток.

Помогите разобраться с решением задачи (https://www.hackerrank.com/contests/w17 ... s-building) с последнего contest'а на HackerRank.

Решение, которое я смог придумать имеет квадратичную сложность, и, в принципе, совпадает с авторским. Но в конце решения автора есть приписка, как улучшить время. И я никак не могу понять что имеется в виду.

Вот она:

Цитата:

... This gives us quadratic solution.


We can get faster solution after we note that we can omit minimum function and write the answer as the sum of max{S−1−D1(X)−DN(Y),0} over all the pairs of (X,Y) such that X and Y are nodes. For calculating this sum, we can just iterate though the nodes X in this sum and use sliding window and prefix sums to calculate the whole sum.

X и Y -- просто вершины в графа. Расстояния D1 и DN от первой и последней вершины до остальных предвычислены. S -- тоже есть.

Как избавиться от квадрата в сумме по всем парам с помощью prefix sum и sliding window?

Спасибо.