公式解説

小課題 1

bit全探索を行うと正解できます。
計算量は $\mathcal O(N 2^N)$ となり十分高速です。

小課題 2

歌えるのは 2人 までなので、歌う人を1, 2人選び全探索すればよいです。

小課題 3

$A_i$ がその順番以上になるように選べばよいです。
これは、以下の DP によって実装できます。

小課題 5

DP 配列の2個目の添字は大きければ良いことが示せます。
よって、$i$ 番目まで見たときの最大の人数を保持すればよいです。

小課題 4

小課題 5 の考え方を用いると、添字を一つにできました。
ここで、あと何人選べるか、という添字を追加し、その時の最大の人数を保持すれば解くことができます。

満点解法

満点を取るには、DP による考えをさらに単純化する必要があります。

まず、 $n+1$ 人で歌えるなら $n$ 人で歌える事を示します。
これは、歌っている中で一番上手い人を外せば良いです。
まだ歌っている $n$ 人にとって、「右の歌う人の条件」についての人数は変わらず、「左の歌う人の条件」については人が減っているので成り立ちます。
よって $n$ 人で歌えるか判定できれば二分探索できます。

二分探索については上手い人から順に、 $i$ 人目の人を自分より上手い人（既に追加した人）を $k$ として $k$ が $A_i$ 人未満で、 $n - k$ が $B_i$ より大きいなら追加すればよいです。

証明

この操作が成功したとき $n$ 人が可能であることは明らかです。
また、$i<j$ で $i$ を選択すると $j$ が選択できなくなる場合でも、双方の重みは同じなので常に選択するのが良いです。
よって、この行動は $n$ 人にするための最善です。

この行動により追加した人数が $n$ 人となれば、 $n$ 人が達成可能であることがわかります。

実装コード（C++, 81ms）