天下一プログラマーコンテスト2016本戦（オープンコンテスト） C - たんごたくさん

問題：C - たんごたくさん

解答：Submission #15800122 - 天下一プログラマーコンテスト2016本戦（オープンコンテスト）

解法：トライ木を使用する。 ei1333.github.io

dp[i]：Sのi文字目までの単語の重みの最大値とする。
あらかじめ各単語をトライ木に格納しておく。トライ木上で文字Sのi番目からみてマッチした単語について、その単語を加味する/加味しないことでdpを更新する。