Click "tasks for printing" or here: https://atcoder.jp/contests/abc163/tasks_print, works for me even though the individual problem pages don't.

For the first 4 minutes, it just was giving Error 502, bad gateway, and now it is loading the problem but all I see is an area to submit code, the text of the task itself is invisible!!

Submit again it will give AC now!!

It's AC now. your submissions

yes

Yes. I'm unhappy to hear that because I solved 4 problems with penalty 27:58 and got the 1017 place. (；′⌒`)

orz first solver

+1

my submission (problem D)

Sort the children according to the Ai(from big to small)

Then if you are considering the i-th child,this is always arranged in the smallest position (aren't used) or the biggest position (aren't used) .

So we can dp.dp[i][j]means when considering the i-th child ,there are j children in the left ,the best answer.

We can update it easily.

UPDATE :SEARCH "Gary" in atcoder for the submission

see HDU 6035 Colorful Tree, after erasing all nodes of color u, find all connected components of the remaining tree and minus the num of paths without passing color u. We can do it by using tree DP like the problem above in $$$O(n)$$$

I want to share my dumb solution. For a color with $$$M$$$ vertice, we can build a virtual tree containing the $$$M$$$ vertice in $$$O(M \log M)$$$. (Don't know if we can do better) Then simply DFS the virtual tree and calculate the number $$$K$$$ of paths in the original graph that doesn't contain the vertex in virtual tree. Te answer for that color is $$$\frac{n (n + 1)}{2} - K$$$.

UPD: turns out it can be done in $$$O(M)$$$ since we don't need sorting in the problem code

true

It's not about the particular browser as far as I understand Some of the responses from the server were cached in the browser during the heavy problems in the beginning. When you tried a different browser, it didn't have the same caches, so it worked fine. But you could just as well refresh the site ignoring the cache or reset it manually (ctrl-shift-R for me)

There is no need to mod in sigma and rsigma.

https://atcoder.jp/contests/abc163/submissions/12138480

This is my code for the problem. spookywooky has given the explanation for the problem.

Can you tell why is max sum n*i — (i(i-1))/2. Like how a proof for that. Thanks :)

I'll assume you already know that we should process the children from the biggest Ai first.

Define dp[l][r] as the maximum happiness we can get if we want to put the remaining children to index l to r. The answer will be dp[1][N]. If the current state is (l, r), that means we are currently processing child with index i = N — (r — l + 1) + 1. We will have two choices, either put this child to index l or index r. If we put it to index l, then the happiness will be abs(l — child_initial_position) * A + dp[l + 1][r]. If we put it to index r, then the happiness will be abs(r — child_initial_position) * A + dp[l][r — 1]. We will take the maximum of those. Hope it helps.

You can have a look at the English commentary of Problem E here.

take the sample 1 3 4 2 as example, the impact of every element in array should like this: [0, 1, 2, 3] [3, 0, 3, 6] [8, 4, 0, 4] [6, 4, 2, 0] it is easy to know that for every element, the impact of it is increasing whit itself like the element 4, the position is 3 then the effect of position of 4, 2, 1 is 4, 4, 8

now you can see that like two element ai and aj, ai>aj, both ai and aj wants position k, we need to put ai at k because: first put all ai and aj to k: (ai*(k-x))+(aj*(k-y)) now we need to move one to k-1 because just one can put to k, if we move ai we need minus ai, move aj we need minus aj, because ai>aj, so put ai at k is better.

Can you tell me how you got this?

In principle this is correct. There must be some of by one error, maybe caused by the fact that the first element in the set is 0.

mod=1e9+7.check it once

Try using the tasks for printing feature: https://atcoder.jp/contests/abc163/tasks_print

Similar problem statement, but not same. In atcoder C, we just had to print the frequencies.