No.1096 Range Sums
Problem Statement
You are given a sequence $A_1, A_2, \cdots, A_N$ with $N$ elements.
For integers $l, r$ such that $1 \leq l \leq r \leq N$, let $S(l,r)=\displaystyle\sum_{k=l}^{r}A_k=A_l+A_{l+1}+\cdots+A_r$.
Find the sum of $S(l,r)$ over all pairs of integers $(l,r)$ satisfying $1 \leq l \leq r \leq N$.
Input
$N$ $A_1 \ A_2 \ \cdots \ A_N$
The input satisfies the following constraints.
- All input values are integers.
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^6 (1 \leq i \leq N)$
- The answer is at most $10^{18}$.
Output
Output the answer on a single line.
Sample
Sample 1
Input
3 3 4 5
Output
40
$S(1,1)=3$
$S(1,2)=3+4=7$
$S(1,3)=3+4+5=12$
$S(2,2)=4$
$S(2,3)=4+5=9$
$S(3,3)=5$
Therefore, output their total, $40$.
Sample 2
Input
5 2 12 7 0 15
Output
244
The sequence $A$ may contain $0$.
Sample 3
Input
1 0
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SSRS
leafirby