Bingo (AOJ 0537)

問題

略

解法

DPで解く。普通に考えるとだが、Mに関しての総和を持っておくとに落ちる。さらに途中ででかい数値を使うとどう頑張ってもSを超える場合があるので、その場合をスキップすることにより枝刈りが効いて間にあうようになる。
MLEも厳しいのでDPの配列は完全に使い回してMS分しか確保しないようにする。