問題一覧 > 通常問題

No.2938 Sigma Sigma Distance Distance Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 161
作問者 : kazuppa / テスター : yuusaan kakao745 hirayuu_yc
0 ProblemId : 11350 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-18 21:43:18

問題文

長さ NN の整数列 A1,A2, ... ,ANA_1,A_2,\ ...\ , A_{N} が与えられます。\\ (∑i=1N∑j=1N ∣i−j∣×∣Ai−Aj∣)\left(\displaystyle\sum_{i=1}^{N}\displaystyle\sum_{j=1}^{N} \ \left|i-j\right| \times \left|A_i-A_j\right|\right) を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
NN
A1  A2 ... ANA_1\ \ A_2\ ... \ A_{N}

制約

  • 1≤N≤1001\leq N\leq 100
  • 1≤Ai≤100(1≤i≤N)1\leq A_i\leq 100(1\leq i\leq N)\\
  • 入力はすべて整数
また、この問題にはAC判定とは関係のないevilケースが用意されています。余力のある人は挑戦してみてください。

evilケースの制約
  • 1≤N≤2×1051\leq N\leq 2\times 10^5
  • 1≤Ai≤500(1≤i≤N)1\leq A_i\leq 500(1\leq i\leq N)
  • 入力はすべて整数
なお、evilケースに挑戦しない人は、入力が通常制約に満たさなかった場合に即座にプログラムを終了していただけると、ジャッジが早く終了します。

出力

(∑i=1N∑j=1N ∣i−j∣×∣Ai−Aj∣)\left(\displaystyle\sum_{i=1}^{N}\displaystyle\sum_{j=1}^{N} \ \left|i-j\right| \times \left|A_i-A_j\right|\right) を一行で出力し、最後に改行してください。

サンプル

サンプル1
入力
2
3 2
出力
2

各 (i,j)(i,j) における (∣i−j∣×∣Ai−Aj∣)(|i-j| \times |A_i-A_j|) は次のようになります。

  • (1,1)=∣1−1∣×∣A1−A1∣=0(1,1)=|1-1|\times |A_1-A_1|=0
  • (1,2)=∣1−2∣×∣A1−A2∣=1(1,2)=|1-2|\times |A_1-A_2|=1
  • (2,1)=∣2−1∣×∣A2−A1∣=1(2,1)=|2-1|\times |A_2-A_1|=1
  • (2,2)=∣2−2∣×∣A2−A2∣=0(2,2)=|2-2|\times |A_2-A_2|=0
    • よって、答えは 0+1+1+0=20+1+1+0=2 となります。

    サンプル2
    入力
    3
1 2 3
    出力
    12

    サンプル3
    入力
    9
41 15 76 69 70 58 10 20 34
    出力
    7196

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。