Eid Mubarak ! Happy Eid-ul-Fitr !!

This picture reminds me of this song.

The guy she told you not to worry about is Tourist.

Let me do this job for you.

Is is Rated (for Div1)?
Ans seems Yes.

MikeMirzayanov awoo Please fix it.
Everyone is registered as "Contestants".
Mark me and others as "out of competition".

we all love pik misha :D

LoOOoOOooOooLoOOOoooOOOoOOLoOoOooOoooooOOL. ROFL. LMAO.
Problems at usual contests: "use a segment tree with some trciky operations and tricky queries"
Problems at educationals: "use a trivial segment tree, (yes) and queries are in the form of $$$[p_i,i]$$$
didn't you feel that difference?"

I'm a wolf! awoo~

true

Best Girl is also Best boy

Baraa_Armoush ur logic hhhhhhh

I wonder why im getting downvotes...am I wrong?

There is always "A worse" in CF...

why?In my opinion this problem is cool.

Expand the summation using prefix sums everywhere

Problem B is just a simple stack based problem of evaluating parenthesized expressions.

And as for signal, check the documentation. signal.alarm is unix only

throw new JokeTooOldException();

D was quite solvable

C is extremely hard to me. lol In my opinion D is easier than C. :)

Create sparse table such that nxt[i][j] is the maximum index sucht that [i, nxt[i][j] ] can be covered using atmost $$$2^j$$$ segments.

Let 1, x2, x3,...,n be index where new subarray starts. Then answer is f(1)×1 + (f(x2)-f(1))×2+....+(f(n)-f(x_k-2))×k. Open it. f(i) is prefix sum till i'th element.

You can extend this proof to general k segments

No you can't 55147246

No. because the f(x) might be something like sin(x) (just for imagination!). suppose there are k + 1 points close to each other, then a huge gap then again k + 1 points close to each other, then a huge gap and so on...

Average of points which have k-1 given integers between them.

My solution lets find minimal distance using binary search. Suppose the answer is X.

Then, our answer point should be in the distance X for at least k points.

Second part is just easy to check if there is a point where k segment intersect [a_i — X, a_i + X].

Complexity O(n * log^2)

But can be easily implemented in O(n * log)

Have you solved it? Well, supose X is outside the range we are right now. Then its better to put it inside the range, to decrease the distances of the k consecutives elements. The ans is the min middle point of all ranges with lenght K. (the best point is the middle one because it gives us the least k minimum differences).

After the Hacking Phase

https://codeforces.net/blog/entry/67411?#comment-516189

Let's invent dp0[i][j] and dp1[i][j].
dp0[i][j] is answer for prefix of length i if we divide into j subsegments
dp1[i][j] is answer for prefix of length i if we divide into j subsegments such as maximum on the last segment (ending at j) is a[i].
First, let's learn how to calculate dp1[i][j].
We find such minimal l that maximum on segment [l; i] is a[i]. Then dp1[i][j] = max(dp1[k-1][j-1] + a[i] * (i — k + 1)) for k in [l; i]. We can notice that we are able to recalc it in O(log n) time using sparse table and Li-Chao tree.
How to recalc dp0[i][j]. Let's notice that if we recalc it as max(dp1[k-1][j] + a[k] * (i — k + 1)) for k in [j; i] we will get right answer (we can't make it better than it is, because the if we fix left bound, bigger right bound means not lower maximum value). Notice that it can be recalced using Li-Chao tree in O(log n). Total complexity is O(nk log n)

D̶&̶C̶ ̶D̶P̶ ̶o̶p̶t̶i̶m̶i̶z̶a̶t̶i̶o̶n̶ I'm actually not sure(there is no editorial for task, so I wrote what i remembered it was), thx for pointing it out

By the way, the problem is not original, statement is only in romanian though

I have an $$$O(NKlog)$$$ solution for G but still havent been able to implement it until now which ruins my rating as always :)

So we lets denote $$$MAX(L, R)$$$ be the maximum value in the subarray $$$[L, R]$$$, and $$$F(i, j)$$$ as the minimum weight of splitting first $$$i$$$ elements to $$$k$$$ subsegments.

By that, we have $$$F(i, j) = min(F(x, j - 1) + MAX(x, i) * (x - i + 1)))$$$ for every $$$x ≤ i$$$.

Lets have an observation:

We can separate $$$(i - x + 1) * MAX(x, i)$$$ to $$$(i - 1) * MAX(x, i) - x * MAX(x, i)$$$. As always, we will have some data structre like Convex Hull or Lichao Tree to query for the minimum $$$w* MAX(x, i) - x * MAX(x, i) + F(x, j - 1)$$$ for $$$w = i - 1$$$.

Now, normally, one will always think of idea of iterating elements from left to right, maintaining the stack of maximum elements and trying to do something about deleting and pushing elements to that stack. As every time $$$MAX(x, i)$$$ changes, we will need to reset our Convex Hull or Lichao Tree over again.

Lets fix $$$i$$$. Now our stack will represent the changes of the $$$MAX(x, i)$$$ if we iterates $$$x$$$ from $$$i$$$ to the left. And for every fixed $$$k$$$, the elements that satisfy $$$MAX(x, i) = k$$$ lies on a continuous subarray. So my main idea is for each $$$k$$$, i will first find the $$$x$$$ that minimizes $$$-x * k + F(x, j - 1)$$$ before we actually inserting it to our Lichao/Convex Hull.

To do this, you can think of an segment tree which each of its node has a Convex Hull or Lichao tree to take this query. And we will use Convex Hull in this case. If we notice that every time we try to change the $$$MAX$$$ of some subarray by deleting some elements from our stack, their $$$MAX$$$ only gets bigger and bigger. So if we use Convex Hull, we can actually handle queries in $$$O(1)$$$ by using the pointer trick instead of binary searching.

Now once we get the best $$$x$$$ for our $$$k$$$, we will insert a line $$$(k, -x * k + F(x, j - 1))$$$ to our Lichao Tree and take queries later.

But another thing to notice is that if some elements are poped out from our stack, the Lichao tree should also be changed. But luckily, only the top elements are deleted from our stack so its prefix is still the same. Here, we can use a persistent Lichao Tree to handle this case.

So my time complexity is actually $$$O(NKlogC)$$$ for building the segment tree of ConvexHull and $$$O(Nlog)$$$ memory for having a persistent Lichao Tree.

Since this solution is pretty much disgusting, I hope its not author's solution. But i dont want his solution to be $$$O(Nkloglog)$$$ either cause I didn't expect it to pass and spent all my contest thinking of a better (not the one above lol) one.