No.393

顧客の要望は昇順にソートしておく.

まずは短い要望から順番に2本の竹に貪欲法で割り当てていく. このとき $k$ 個の要望に応えたとする. $k = m$ ならばすべての要望に応えられる.

そうでない場合は, 2本の竹の余りの長さ $w_1, w_2$ を考えたとき, $w_1 + w_2 \geq A_{k+1}$ ならば $k+1$ 個の要望に応えられる可能性がある.

なお, $w_1 \lt A_{k+1}$, $w_2 \lt A_{k+1}$, $A_{k+1} \leq A_{k+2}$ であるので, $w_1 + w_2 \lt 2A_{k+1} \leq A_{k+1} + A_{k+2}$ となるので, $k+2$ 個以上の要望に応えることはできない.

次に $A_1 \dots A_k$ の要望で作れる長さを DP で求める. これはビットORとビットシフトで計算できるので高速化できる.

そして $x = w_1 + w_2 - A_{k+1}$ としたとき, $[n_1 - x, n_1]$ または $[n_2 - x, n_2]$ の区間でひとつでもその長さが作れるかどうかを見る. 作れるならば $k+1$ 個の要望に答えられる.