Formation Of Idol Unit

愚直に実装することを考えると、${}_N C_M$通りを全探索し、「魅力度」の最大値を求めることになりそうです。しかし、その方針では TLE(実行時間制限超過)となり、正解することはできません。
そこで、$M$ の値で場合分けを行います。

• $M = 1$ のとき、愚直に求める $O({}_N C_1) = O(N)$ で正解できます。

• $M \geq 3$ のとき、以下のように解くことができます。
  事務所に所属するアイドル全員の、「Vi」ステータスの集合を $All_{Vi}$ 、「Da」ステータスの集合を $All_{Da}$ 、「Vo」ステータスの集合を $All_{Vo}$ としたとき、答えは $\mathrm{max}(All_{Vi}) + \mathrm{max}(All_{Da}) + \mathrm{max}(All_{Vo})$ です。
  何故なら、$3$ 人以上選べるとき、各ステータスの最大値を持つアイドルを採用することができるからです。これは、 $O(N)$ で求められます。

• $M = 2$ のとき、以下のように解くことができます。
  二人のアイドルとして、$i,j$ 番目のアイドルを選んだとき、ユニットの「魅力度」は以下で表される式のいずれかになります。

  • $A_i + B_i + C_i$
  • $A_i + B_i + C_j$
  • $A_i + B_j + C_i$
  • $A_i + B_j + C_j$
  • $A_j + B_i + C_i$
  • $A_j + B_i + C_j$
  • $A_j + B_j + C_i$
  • $A_j + B_j + C_j$

  上のそれぞれの場合において、取りうる「魅力度」の最大値は $O(N)$ で求めることができ、それらの最大値が答えになります。

よって、 $O(N)$ で十分高速にこの問題に正解できます。

以下に Python の実装例を示します。