問題一覧 > 通常問題

No.2284 Assembly

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 89
作問者 : みここみここ / テスター : AngrySadEightAngrySadEight cureskolcureskol 👑 potato167potato167
5 ProblemId : 9169 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-23 09:04:50

問題文

$N$ 個の椅子が前後一列に並んでいます。これらの椅子にははじめ誰も座っていません。

これから $N$ 人の学生が一人ずつ順番に椅子に座っていきます。$i$ 番目に椅子に座る学生には正整数 $A_i$, $B_i$ が割り振られています。

各学生はその時点で誰も座っていない椅子のうち、最も前または最も後ろにある椅子に座ります。

最終的に各 $i$ 番目の学生が前から $P_i$ 番目の椅子に座るとき、学生の座り方は $P$ であるといい、座り方 $P$ における $i$ 番目の学生の嬉しさ $f_P(i)$ を $f_P(i) = \sum_{j : P_j < P_i}A_iB_j $ と定めます。

すべての座り方 $P$ の中で学生のうれしさの総和 $\sum_{i = 1}^{N}f_P(i)$ が最大となるときの値を求めてください。

入力

$N$
$A_1 \ B_1$
$\vdots$
$A_N \ B_N$
  • 入力される値はすべて整数
  • $1 \le N \le 2 \times 10^5$
  • $1 \le A_i \le 10^4$
  • $1 \le B_i \le 10^4$

出力

答えを出力してください。

サンプル

サンプル1
入力
3
7 3
10 1
2 5
出力
92

$1$ 番目の学生が後ろ側に、$2$ 番目の学生が後ろ側に、$3$ 番目の学生が前側に座ったとき、$1$ 番目の学生は前から $3$ 番目の椅子に、$2$ 番目の学生は前から $2$ 番目の椅子に、$3$ 番目の学生は前から $1$ 番目の椅子に座ります。すなわち、座り方 $P$ は $(3, 2, 1)$ となります。このとき、$P$ における各学生の嬉しさは

  • $f_P(1) = A_1B_2 + A_1B_3 = 42$
  • $f_P(2) = A_2B_3 = 50$
  • $f_P(3) = 0$

となるので、嬉しさの総和は $92$ となり、これが最大となります。

$P = (2, 3, 1)$ となる座り方はできないことに注意してください。

サンプル2
入力
7
3 6
1 5
4 3
1 5
5 8
9 9
2 7
出力
584

$P = (1, 2, 7, 3, 4, 6, 5)$ のときに嬉しさの総和が $584$ となり、これが最大となります。

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

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