Draw parabolas satisfying the given condition. Then, an envelope appears *1.This is similar to the convex hull. Actually, Graham scan *2 also works in this case. There is another solution using the the convex hull of (x[i],y[i]-x[i]*x[i]).…

https://atcoder.jp/contests/exawizards2019/tasksDynamic programming. Look at the elements in ascending order.Let dp[i][j] be the answer of the sub problem replacing a[0],...,a[N-1] with a[0],...,a[i-1] and replacing X with j. Suppose a[0] …