問題一覧 > 通常問題

No.844 split game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 148
作問者 : sinsincoscossinsincoscos / テスター : tempura_pptempura_pp
14 ProblemId : 2810 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-11-18 01:48:57

問題文

umgくんは$1\times 1$のマスが横に$N$個並んだマス目を使ったゲームを遊ぶことにしました。左から$i$番目のマスをマス$i$と呼ぶことにします。 ゲームのルールは以下のようになっています。
・$1\le i \le N-1$をみたす整数$i$を$1$つ選んでマス$i$とマス$i+1$の間に黒い線を引く。$1$本引くごとに,umgくんは$A$点を失う。この操作を好きな回数繰り返す。つまり,黒線は何本引いてもよいし,$1$本も引かなくてもよい。
・$M$個の区間$[l_j,r_j] \ (1\le j \le M)$が与えられる。区間$[l_j,r_j]$が存在するとき,umgくんは$p_j$点を得る。ただし,区間$[l_j,r_j]$が存在するとは,以下の2つの条件を満たすことを言う。
 1. マス$l_j-1$とマス$l_j$の間,マス$r_j$とマス$r_j+1$の間にそれぞれ黒線が存在する。ただし,マス目$1$の左側と,マス目$N$の右側には最初から黒線が引いてあると考えてよい。
 2. マス$l_j$からマス$r_j$の間に黒線は$1$本もない。より正確に言えば,$l_j \le i \lt r_j$をみたすすべての整数$i$について,マス$i$とマス$i+1$の間に黒線はない。
umgくんが適切に黒線を引いたときに得られる得点の最大値を求めてください。

入力

$N\ M\ A$
$l_1 \ r_1 \ p_1$
$l_2 \ r_2 \ p_2$
$\vdots$
$l_M \ r_M \ p_M$

$2 \le N \le 10^5$
$1 \le M \le \min(10^5, \frac{N(N+1)}{2})$
$1 \le A \le 10^9$
$1 \le l_j \le r_j \le N$
$i\neq j$のとき,$(l_i,r_i)\neq (l_j,r_j)$
$1 \le p_j \le 10^9$

出力

答えを表す数値を1行に出力してください。 最後に改行してください。

サンプル

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

マス1とマス2の間に黒線を引くと1点を失いますが,区間$[2,5]$ができて10点が得られるので,計9点となります。これが最適です。

サンプル2
入力
5 2 1
1 1 2
2 5 10
出力
11

マス1とマス2の間に黒線を引くと1点を失いますが,区間$[1,1]$と$[2,5]$ができて12点が得られるので,計11点となります。これが最適です。

サンプル3
入力
5 2 100
1 3 5
2 4 10
出力
0

黒線を引くコストが大きすぎるので,何もしないことが最適です。

サンプル4
入力
6 9 310889455
1 3 811332240
4 5 729061888
1 5 837866464
1 1 71272252
2 3 175965136
3 6 324033005
2 5 922077575
3 4 396994878
2 4 897759396
出力
918615218

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