試験を で昇順に並べておきます
選ぶ試験の集合を と置くと、明らかに太郎くんは
の問題を全て解くとして良いです。
したがって、 が成り立ちます。
また、次郎くんは を番号が小さい順に解きます。
従って、次郎くんが解いた問題のうち最も番号が大きいものを
と置くと、[tex:T-\sum{i \leq k} B_i < min{B_i \mid i>k , i\in S}] が成り立ちます。
mn[i][j] を 仕事[0,i)まで見た時、次郎くんの使用時間がjになるような仕事の選び方で太郎くんの使用時間が最小になるもの
mx[i][j] を 仕事[i,n)まで見た時、太郎くんの使用時間がj以下になるような仕事の選び方で太郎くんのこなした仕事量が最大のもの
と置きます。
mn[i][j] で選ぶ仕事は全て二人ともこなす仕事、mx[i][j] で選ぶ仕事は太郎くんのみがこなす仕事です。
この二つの配列から頑張ると解けます。
