No.1096 Range Sums
タグ : / 解いたユーザー数 302
作問者 :
SSRS
/ テスター :
mfbgjscz
問題文
要素数$N$の数列$A_1, A_2, \cdots, A_N$が与えられます。
$1 \leq l \leq r \leq N$なる整数$l, r$に対し、$S(l,r)=\displaystyle\sum_{k=l}^{r}A_k=A_l+A_{l+1}+\cdots+A_r$とします。
$1 \leq l \leq r \leq N$を満たす整数$(l,r)$の組すべてに対する$S(l,r)$の和を求めてください。
入力
$N$ $A_1 \ A_2 \ \cdots \ A_N$
入力は以下の制約を満たします。
- 入力はすべて整数
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^6 (1 \leq i \leq N)$
- 答えは$10^{18}$以下である
出力
答えを一行に出力してください。
サンプル
サンプル1
入力
3 3 4 5
出力
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$
となります。よって、これらの総和である$40$を出力します。
サンプル2
入力
5 2 12 7 0 15
出力
244
数列$A$に$0$が含まれることもあります。
サンプル3
入力
1 0
出力
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。