Problem 3: Inquiry

https://open.kattis.com/problems/inquiryi

Trivial approach:

calculate the value for all $k$ separately

The time complexity is $O(n^2)$. Since $n\leq 10^6$, this is too slow

Hints:

Do we have to calculate $(a_1^2 + a_2^2 + \cdots + a_k^2) \cdot (a_{k+1} + \cdots + a_n)$every single time?

Can we store some intermediate value in $(a_1^2 + a_2^2 + \cdots + a_k^2) \cdot (a_{k+1} + \cdots + a_n)$ so that we we can save ourselves some work for the next product?

Key idea:

1. Store $a_1^2 + \cdots + a_k^2$as $S_1$. Store $a_{k+1} + \cdots + a_n$ as $S_2$

2. For k= 1 ... n: we add $a_{k+1}^2$ to $S_1$ and subtract $a_{k+1}$from $S_2$.

Remember to use type long long for this problem.