問題一覧 > 通常問題

No.2321 Continuous Flip

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : 👑 amentorimaruamentorimaru / テスター : tatyamtatyam
16 ProblemId : 9200 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-31 16:57:41

問題文

エトワーニュくんがカードゲームのワールドで遊んでいます。かわいいですね。


$N$ 枚のカードが裏向きに並べられており、$1$ から $N$ までの番号がつけられています。カード $i$ の表面には整数 $A_i$ が書かれています。裏面には何も書かれていません。

エトワーニュくんは次の操作を好きな回数（ $0$ 回でも良い）行うことができます。

  • $1$ 以上 $M$ 以下の整数 $i$ を $1$ つ選び、カード $L_i, L_i + 1, \dots, R_i$ の表裏を返す

エトワーニュくんは全ての操作を終えたとき、操作を行った回数を $X$ 、表向きのカードに書かれている整数の合計を $S$ として、$S - X \times C$ の幸福度を得ます。

エトワーニュくんが得られる最大の幸福度を求めてください。

入力

$N$ $M$ $C$
$A_1$ $A_2$ $\cdots$ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$
  • 入力は全て整数
  • $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$

出力

答えを出力せよ。

サンプル

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

エトワーニュくんは、$i = 1, 2, 3$ の順に操作を行うことで、カード $1,3,4,5$ を表向きにすることができます。このとき、$X = 3, S = 5 + 5 + 6 + 6 = 22$ より幸福度は $S - X \times C = 19$ となり、これが最大です。

カード $2$ は $i = 1, 2$ の操作で $2$ 回裏返したため裏に戻っていることに注意しましょう。

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

エトワーニュくんは $3$ つの操作を $1$ 回ずつ行うことで全てのカードを表にすることができますが、$i = 1$ の操作を $1$ 回だけ行う方が幸せになります。

サンプル3
入力
3 6 100
1 1 1
1 1
1 2
1 3
2 2
2 3
3 3
出力
0

エトワーニュくんはカードを全て裏向きの状態から何もせずにぼうっとしているのが一番幸せです。かわいいですね。

サンプル4
入力
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
出力
945

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