原因として想定していた解法(メモ化再帰)でジャッジデータのoutを作るにあたりdpテーブルを必要な分より小さく確保したままメモ化再帰をしていたことが原因です。元に戻した結果MLEすることが判明しました。
これを想定していた解法でも解けるように制約を修正し、ジャッジデータを作り直します。すみませんでした。
問題
つくば市に住むジョーイ君は最近曲作りにはまっています。
ジョーイ君はN個のフレーズをすでに用意しています。各フレーズには盛り上がり度Gと基準となるフレーズの速さTが決められており、１つ前のフレーズの速さとの差の絶対値とフレーズの盛り上がり度を掛け合わせたものがそのフレーズの最終的な盛り上がり度となります。
また、全てのフレーズの最終的な盛り上がり度の総和が曲の盛り上がり度となり、ジョーイ君はこの曲の盛り上がり度を出来る限り大きくするように各フレーズの速さを調節します。(フレーズを流す順番はすでに決まっています。)
各フレーズの速さは、フレーズiの基準となる早さをTiとしたとき、Ti-RiからTi+Riまでに調節することが出来ます。
ただし、速さは必ず整数にしなければいけません。
また、条件として、各フレーズの、前のフレーズの速さとの差の絶対値の総和がPを超えてはいけません。
あなたはジョーイ君が曲の盛り上がり度が最大になるように各フレーズの速さを調節した場合、曲の盛り上がり度がどのくらいになるのかを調べることにしました。
入力
N P T1 R1 G1 T2 R2 G2 . . . TN RN GN
１行目にフレーズの数Nと、フレーズの速さの差の絶対値の総和の上限Pが整数で空白区切りで与えられる。
2行目からはN行にかけて、i(1≦i≦N)番目に使われるフレーズの情報が与えられる。Tiはi番目のフレーズの基準となるフレーズの速さを、Riはそのフレーズの速さを調節できる範囲を、Giはそのフレーズの盛り上がり度を表している。
出力
ジョーイ君が出来るだけ曲の盛り上がり度が最大になるように曲を作った場合の、曲の盛り上がり度を１行に出力する。
制約
全ての入出力ケースについて以下を満たす。
- 1≦N≦100
- 1≦P≦3000
- 1≦Ti-R≦Ti≦Ti+R≦50
- 1≦Gi≦1000
- 必ず条件を満たした曲を少なくとも１つは作ることが出来る。
入出力例
入力例1
3 10 5 0 2 1 0 6 3 0 4
出力例1
32
解説
この入出力例はすべてのフレーズの速さの調節できる範囲が0のため、作れる曲のパターンは１つのみとなります。
この時、曲の盛り上がり度はこのようにして求まります。
１つめのフレーズの速さと２つめのフレーズの速さの差の絶対値は|5-1|=4となり、これに２つめのフレーズの盛り上がり度の6を掛けた値の24が２つめのフレーズの最終的な盛り上がり度になります。
２つめのフレーズの速さと３つめのフレーズの速さの差の絶対値は|1-3|=2となり、これに３つめのフレーズの盛り上がり度の4を掛けた値の8が２つめのフレーズの最終的な盛り上がり度になります。
絶対値の総和は4+2=6となり、10以下なので、この時条件を満たしています。
曲の盛り上がり度は24+8=32となり、これが答えとなります。
入力例2
3 10 5 3 2 1 0 6 3 2 4
出力例2
54
解説
この入出力例はすべてのフレーズの速さの調節できる範囲が0のため、作れる曲のパターンは複数あります。その中で最も曲の盛り上がり度が大きくなるようにするには次のようにします。
この時、曲の盛り上がり度はこのようにして求まります。
１つめのフレーズの速さを8、２つめのフレーズの速さを1、３つめのフレーズの速さを4とします。
１つめのフレーズの速さと２つめのフレーズの速さの差の絶対値は|8-1|=7となり、これに２つめのフレーズの盛り上がり度の6を掛けた値の42が２つめのフレーズの最終的な盛り上がり度になります。
２つめのフレーズの速さと３つめのフレーズの速さの差の絶対値は|1-4|=3となり、これに３つめのフレーズの盛り上がり度の4を掛けた値の12が２つめのフレーズの最終的な盛り上がり度になります。
絶対値の総和は7+3=10となり、10以下なので、この時条件を満たしています。
曲の盛り上がり度は42+12=54となり、これが答えとなります。
入力例3
1 1000 25 24 1000
出力例3
0
解説
フレーズが１つしかないとき、前のフレーズとの差は１つもないため、0となります。
入力例4
10 233 20 6 840 15 1 202 26 2 586 27 19 614 14 9 956 24 9 690 44 0 901 24 13 386 33 5 226 33 14 691
出力例4
125986