簡単のため、価格 \(a, b\) は降順にソートされているものとします。

\(l := \lceil{\sqrt{L+1} \rceil}\) とすると、最も価格の高い定食は

• 主菜の価格が \(a_1, a_2, \ldots, a_l\) のいずれか
• 副菜の価格が \(b_1, b_2, \ldots, b_l\) のいずれか

のどちらかを必ず満たします（両方の条件を満たさない任意の定食に対し、それ以上に高価な組み合わせが \(L+1\) 個以上存在するため）。

したがって、\((a_1, a_2, \ldots, a_l) \times (b_1, b_2, \ldots, b_M)\) または \((a_1, a_2, \ldots, a_N) \times (b_1, b_2, \ldots, b_l)\) という組み合わせを全探索すればよいです。

計算量は \(O((N+M) \sqrt{L} + (N+M)\log{(N+M)})\) 時間です。

実装例

さらに工夫することで \(O(L \log{L} + (N+M)\log{(N+M)})\) 時間の解法になります。

再び、価格 \(a, b\) は降順にソートされているものとします。また、インデックス \(i, j\) は 1-based とします。

自身以上に高価な組み合わせが \(L+1\) 個より多く存在する場合、その組み合わせは最も価格の高い定食になりえません。 したがって、\(i \times j \leq L+1\) を満たす \((a_i, b_j)\) の組だけ調べれば十分です。

このとき、ソートを除いた計算量は \(O(L \log{L})\) 時間になります。

実装例