答えを二分探索します。簡単のため、アリは開始時点の座標値で昇順にソートされているものとします。

答えが \(t\) 秒以上であるためには、\(k\) 匹以下のアリを取り除くことで \(t\) 秒後のアリの座標値が(広義)単調増加にできることが必要十分です。これは数列の LIS を求めることで判定できます。

計算量は \(O(N \log(N) \log(\max (t))\) です。