問題一覧 > 通常問題

No.844 split game

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

問題文

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

入力

N M A
l1 r1 p1
l2 r2 p2

lM rM pM

2N105
1Mmin(105,N(N+1)2)
1A109
1ljrjN
ijのとき,(li,ri)(lj,rj)
1pj109

出力

答えを表す数値を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もしくは右上の雲マークをクリックしてアカウントを作成してください。