問題一覧 > 通常問題

No.3470 実行時間の差の合計

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 : yuki2006
ProblemId : 2213 / yukicoder 2026新ジャッジ contest (順位表) / 自分の提出
問題文最終更新日: 2026-03-06 20:14:03
yukicoder 2026新ジャッジ contestの他の問題:

問題文

$N$ 件の提出があります。$i$ 番目の提出の実行時間は $T_i$ ミリ秒です。

すべてのペア $(i, j)$ ($1 \le i < j \le N$) に対する実行時間の差の絶対値 $|T_i - T_j|$ の合計を求めてください。

入力

$N$
$T_1\ T_2\ \ldots\ T_N$
制約はすべて整数

  • $2 \le N \le 200{,}000$
  • $0 \le T_i \le 10^8$

部分点

この問題にはサブタスクによる部分点が設定されています。

サブタスク名配点制約
small40 点N ≤ 1,000
large30 点追加の制約なし
ランダムlarge30 点追加の制約なし

出力

$\displaystyle\sum_{1 \le i < j \le N} |T_i - T_j|$ を 1 行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
1 3 6
出力
10

$|1-3| + |1-6| + |3-6| = 2 + 5 + 3 = 10$

サンプル2
入力
4
5 5 5 5
出力
0

すべて同じ値なので差は 0 です。

サンプル3
入力
5
1 2 3 4 5
出力
20

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