No.2321 Continuous Flip
タグ : / 解いたユーザー数 37
作問者 : 👑
amentorimaru
/ テスター :
tatyam
Problem Statement
Etowanyu-kun is playing in the world of card games. Isn't he cute?
$N$ cards are lined up face down, numbered from $1$ to $N$. The integer $A_i$ is written on the front of card $i$. Nothing is written on the back.
Etowanyu-kun can perform the following operation any number of times (possibly $0$ times).
- Choose $1$ integer $i$ between $1$ and $M$, inclusive, and flip cards $L_i, L_i + 1, \dots, R_i$ over.
When he has finished all his operations, let $X$ be the number of operations he performed and $S$ be the sum of the integers written on the face-up cards. He then gains a happiness of $S - X \times C$.
Find the maximum happiness Etowanyu-kun can gain.
Input
$N$ $M$ $C$ $A_1$ $A_2$ $\cdots$ $A_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_M$ $R_M$
- All inputs are integers.
- $1 \le N, M \le 2 \times 10^5$
- $1 \le A_i, C \le 10^9$
- $1 \le L_i \le R_i \le N$
Output
Output the answer.
Sample
Sample 1
Input
6 4 1 5 3 5 6 6 4 1 2 2 3 4 5 5 6
Output
19
By performing the operations in the order $i = 1, 2, 3$, Etowanyu-kun can make cards $1,3,4,5$ face up. In this case, $X = 3, S = 5 + 5 + 6 + 6 = 22$, so the happiness is $S - X \times C = 19$, which is the maximum.
Note that card $2$ was flipped $2$ times by the operations $i = 1, 2$, so it has returned to face down.
Sample 2
Input
5 3 3 5 5 1 1 4 1 4 3 4 3 5
Output
9
Etowanyu-kun can make all the cards face up by performing each of the $3$ operations $1$ time, but he is happier performing the operation $i = 1$ just $1$ time.
Sample 3
Input
3 6 100 1 1 1 1 1 1 2 1 3 2 2 2 3 3 3
Output
0
Etowanyu-kun is happiest doing nothing and idly zoning out with all the cards left face down. Isn't he cute?
Sample 4
Input
20 20 20 42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 5 12 3 14 3 13 2 17 16 19 7 8 12 19 10 13 8 20 15 16 4 12 3 14 5 14 2 12 9 14 5 8 3 18 18 20 2 4 10 19
Output
945
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。