No.2284 Assembly
タグ : / 解いたユーザー数 92
作問者 :
みここ
/ テスター :
cureskol
👑 Problem Statement
$N$ chairs are lined up in a single row from front to back. Initially, no one is sitting on these chairs.
Now, $N$ students will sit down on the chairs one at a time, in order. The student who sits down $i$-th is assigned positive integers $A_i$, $B_i$.
Each student sits on either the frontmost or the rearmost chair among the chairs that are unoccupied at that moment.
When, in the end, each $i$-th student sits on the $P_i$-th chair from the front, the seating arrangement of the students is said to be $P$, and the happiness $f_P(i)$ of the $i$-th student in the seating arrangement $P$ is defined as $f_P(i) = \sum_{j : P_j < P_i}A_iB_j $.
Find the maximum value of the total happiness of the students $\sum_{i = 1}^{N}f_P(i)$ over all seating arrangements $P$.
Input
$N$ $A_1 \ B_1$ $\vdots$ $A_N \ B_N$
- All input values are integers.
- $1 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^4$
- $1 \le B_i \le 10^4$
Output
Output the answer.
Sample
Sample 1
Input
3 7 3 10 1 2 5
Output
92
When the $1$-st student sits at the rear, the $2$-nd student sits at the rear, and the $3$-rd student sits at the front, the $1$-st student sits on the $3$-rd chair from the front, the $2$-nd student sits on the $2$-nd chair from the front, and the $3$-rd student sits on the $1$-st chair from the front. That is, the seating arrangement $P$ is $(3, 2, 1)$. In this case, the happiness of each student in $P$ is as follows:
- $f_P(1) = A_1B_2 + A_1B_3 = 42$
- $f_P(2) = A_2B_3 = 50$
- $f_P(3) = 0$
Thus, the total happiness is $92$, and this is the maximum.
Note that a seating arrangement with $P = (2, 3, 1)$ is not possible.
Sample 2
Input
7 3 6 1 5 4 3 1 5 5 8 9 9 2 7
Output
584
When $P = (1, 2, 7, 3, 4, 6, 5)$, the total happiness is $584$, and this is the maximum.
Sample 3
Input
1 1 1
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。