Google Kickstart 2020のRoundA - Plates問題の解説

Google Kickstart 2020 RoundAのPlatesの問題について、解説をしてみたいと思います。
実装したものは、こちらにあります。

問題の要約

N個のスタックに、それぞれK個の皿があり、それぞれの皿には正の値（beauty value）が書かれている。ここからP個の皿を取り出した場合、その和に関して最大値を求めたいという問題です。

アルゴリズム1(TLE)

N個のスタックから皿を取り出す全パターンを考えて、そのパターンのうち、取り出した数がP個である組み合わせを対象に、和の最大値を求めれば問題を解決できそうです。
この時の全パターンは、スタック１からK個を取り出すそれぞれについて、スタック２からK個を取り出す組み合わせがあり、さらにスタック３からK個を取り出す組み合わせがあり、...、最後スタックNまでK個を取り出す場合の組み合わせとして列挙できるので、$${K^N}$$通りの組み合わせがあります。
このアルゴリズムでは、Test set1は$${1 \leq N \leq 3}$$なのでPass出来ますが、$${1 \leq N \leq 50}$$のTest set2ではTLEとなってしまいます。（$${1 \leq K \leq 30}$$）

アルゴリズム２(Passed)