解法

愚直解に Mo する。$O(N \sqrt{N} \log N)$。

愚直解を考えると $O(N^2 (\log N)^2)$ である。 つまり、まず $K$ を固定し、次をする: 左から高々 $l$ チーム作ったときの値の総和の最大値と、右から高々 $r$ チーム作ったときの値の総和の最大値を、それぞれすべて求め、綴じ合わせる。 中央値を取るための $O(\sum _ {K \le N} \frac{N}{K}) = O(N \log N)$ 回のソートが問題で、これがなければ $O(N \log N)$ である。 これら中央値を Mo’s algorithm で $O(N \sqrt{N} \log N)$ かけて前処理しておけば、全体でも $O(N \sqrt{N} \log N)$ になり、通る。

メモ

  • 愚直 $O(N^2 (\log N)^2)$ をやると手元で $6.5$ 秒ぐらいだった

リンク