C can be solved without the fact that the median of each subarray is also the median of the whole sequence. Let $$$f(l, r)$$$ be the median of $$$a_l, a_{l+1}, \dots, a_r$$$. We fix the median as $$$x$$$, and let $$$dp_i$$$ be the number of subarrays when each one has median $$$x$$$. The idea is we only iterate through all $$$j$$$ such that $$$f(j, i)=x$$$, meaning across all $$$x$$$ there will be $$$O(n^2)$$$ transitions. I'm just unsure if $$$f$$$ can be computed faster than $$$O(n^2 \log n)$$$.

For Maximum Average Subarrays, shouldn't $$$pt_j$$$ be the previous point on the lower hull of the points?

As of writing this comment, it is processing submissions from 7 hours ago, so I think it's gonna take a while. :)

da. god

wasn't able to participate in this contest, but the problems were very good, I think. although G does feel like it reduces down to just applying a standard graph algorithm, no?