この問題は以下の特徴があるため、いわゆる「燃やす埋める」と呼ばれる問題である可能性が考えられます。

• 複数の選択間に対するコストが発生する
• 制約(\(N,M,L\))の値が小さい

この問題は「各選択肢が2つ」、「2つの選択間にコストが発生する」ようなよく見る燃やす埋める問題と異なり、「各選択肢(スキルレベル)が複数ある(最大5つ)」、「複数の選択(スキルレベル)がすべて条件(\(L_{ij}\)以上)を満たすとき利得が発生する」という制約が含まれています。 実はこれらの制約も最小カット問題の制約としてあらわすことができるため、燃やす埋める問題として解くことができます。

(公式解説のように「スキル \(i\) をレベル \(x\) 以上にするか否か」を2択の選択と考えることで通常の燃やす埋める問題として捉えることもできます。というかやってることは同じです)

燃やす埋める問題についての解説

これらの制約を表すグラフを作成することは制約が複雑になるほど面倒になるのでライブラリを作りたくなります。

上の記事にも書いていますが、ライブラリとして欲しい機能としては

• 各選択肢にかかるコストを設定
  • スキル \(i\) をレベル \(j\) にした際のコスト \(C_{i}\times (j-1)\)
• 2つの選択間にかかるコストを設定
  • スキル \(i\) をレベル \(L_i\) に、スキル \(j\) をレベル \(L_j\) にした時コスト \(C_{ij}\) ( \(C_{ij}\) はMongeコスト) (今回の問題にはない制約)
• 複数の選択のうち1つ以上が条件を満たすときにかかるコストを設定
  • 「複数のスキルのレベルがすべて \(L_{ij}\) 以上なら \(A_i\) 円貰える」の逆を考えるとこの制約
  • 選択肢に順序がある(レベルなどの数値)場合に使いがち
• 解の復元
  • 最小コストを達成する各スキルのレベルを答える(今回の問題にはない)

これらを3択以上の選択肢の場合に拡張させておくと便利です。他にも様々な制約を表現する方法がありますので上の記事を参照してください。

解答例(ライブラリ例)を載せておきます。コメントも参考に。

https://atcoder.jp/contests/abc326/submissions/47306818