As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 06:52:10
Last updated: 2025-12-14 06:52:13
二分答案之后可以转化为凸包 DP，时间复杂度 $O(n^3\log C\epsilon^{-1})$。
注意到凸包 DP 时，我们要先枚举一个起点作为最下方的点，如果我们把所有点 shuffle 之后先枚举再二分，并且二分之前先检查一下是否能更新答案，那么期望只需要 $O(n+\log n\log C\epsilon^{-1})$ 次 check（因为前缀 $\max$ 的期望个数是 $O(\log n)$）。
时间复杂度变为 $O(n^2(n+\log n\log C\epsilon^{-1}))$。