1015

違う問題で見かけた陰険インプットを見てひらめいた。実はちゃんとDPできてた。そしてなんで解けないのか分かった。0 0だけで構成されるケースでWAが出てただけでしたorz 道の再構築にsetとか使ってるせいでオーダーがでかくなっちゃってるのでその辺をどうにかしよう。たぶんO(NMlogM)。しかもsetをコピーしてるから係数が超でかい。

考え方としては、table[|P|-|D|]=|P|+|D|として、|P|+|D|が最大になるようにtableを構築していく。一度使ったindexを二度と使わないようにする処理を効率よく実装できれば早くなる希ガス。今日色々作業しながら考えてみる。

追記:
気になって仕方なかったので出かける前に速くしてみたら15msになった。set→unsigned int[7]にしただけとか終わってる。もっと華麗な方法は無い物なのか…。