問題一覧 > 通常問題

No.1096 Range Sums

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 187
作問者 : SSRSSSRS / テスター : leafirbyleafirby
3 ProblemId : 4213 / 出題時の順位表
問題文最終更新日: 2020-06-26 22:15:48

問題文

要素数$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もしくは右上の雲マークをクリックしてアカウントを作成してください。