隣り合う社員の[出かける/戻る]を時刻ごとにソートして考えます。

\[ E_t = (時刻 t に社員iが[外出/帰社]したイベント) \]

を保持します。C++のstd::mapなどの二分木で持つのが良いでしょう。

便宜上、すべての時刻\(t\)で\(E_t\)が定義されていることにします。実際のコードでは\(E_{t+1}\)は\(「E_tの次の要素」\)として読み替えてください。

社員\(i\)が外出する時刻を\(s_i\), 帰社する時刻を\(r_i\)とします。

無条件に鍵を閉めていて良い条件

• 最初に誰かが外出するまでの時間
• 最後に誰かが帰社してからの時間

これらは明らかに誰が鍵を持っていてもよいです。

• \(E_{r_i+1}\)が外出イベントの場合

社員\(i\)が帰社したときに鍵を閉めてればよいので、\([E_{r_i}, E_{r_i+1}]\)のあいだは鍵を閉めていて良いです

鍵を持っていたら閉めていて良い時間がどれだけ増えるか

\(E_{s_i+1}=E_{r_i}\)の場合

鍵を持っていれば、\([E_{s_i}, E_{r_i}]\)のあいだの鍵を閉められます。

\(E_{s_i+1}\)が外出イベントかつ\(E_{r_i-1}\)が帰社イベントの場合

鍵を持っている場合は、

\(s_i+1\)に外出する社員は自力で鍵を開けることができるので外出時には鍵を閉めて良いです。

\(r_i-1\)に帰社する社員に閉めてもらうことができます。

社員\(i\)が鍵を持っていれば、\([E_{s_i}, E_{s_i+1}], [E_{r_i-1}, E_{r_i}]\)のあいだ鍵を閉めて良いです。

\(E_{r_i+1}\)が帰社イベントの場合

社員\(i\)以降で関係を満たす社員を\(O(N)\)で列挙します。

すると、この関係にある社員のイベントは

\[ [外出_1, 外出_2,帰社_1,外出_3, 帰社_2,...外出_{X-1}, 帰社_{X-2}, 外出_{X}, 帰社_{X-1}, 帰社_{X}] \]

となります。

• 最初の社員\(a\)が鍵を持っていれば、\([E_{s_a},E_{s_a+1}]\)の間は閉めていて良い。
• 最後の社員\(b\)が鍵を持っていれば、\([E_{s_b-1},E_{s_b}]\)の間は閉めていて良い。
• 社員\(x\)とその次に出社する社員\(y\)が鍵を持っていれば、\([E_{s_y},E_{r_x}]\)の間は閉めていて良い。

\[ dp_1[k] = これまでk人が鍵を持ち、最後の1人が鍵を持っているときに閉めていて良い時間の最大値 \]

\[ dp_2[k] = これまでk人が鍵を持ち、最後の1人が鍵を持っていないときに閉めていて良い時間の最大値 \]

として動的計画法によって\(O(N^2)\)で解くことができます。

鍵を\(K\)人に持たせて閉められる時間の最大値

上記の条件を組み合わせることで、動的計画法によって\(O(N^2)\)で解くことができます。

解答

「無条件に鍵を閉めて良い時間+鍵を\(K\)人に持たせて閉められる時間の最大値」が答えです。

合計で\(O(N^2)\)で求められます。