https://pasteboard.co/GQNNymL.png

https://pasteboard.co/GQNO1vS.png

Sorry I do not like the sea :( I often get seasick

spoiler:u Got trolled!!

Anyways, the music is good :P

It's just merging 2 to 3 piles of balls every time, with each time the cost.equals to the sum of the number of balls merged, so a greedy algorithm would work.

Think backwards. You have all the elements in their original position and you want to put them in starting position with smallest cost. To solve this, you can adapt the greedy algorithm to find the Huffman code. There are two main differences:

1) You get the 3 smallest elements to generate a new one (instead of two).

2) In the case when you have a even amount of elements you'll get a suboptimal solution if you follow this algorithm. But you can be greedy here too, just convert the smallest two to a new element to get and odd number of elements.

Greedy will work to solve D.The process of D is to build a Huffman Tree.So we can construct a Huffman Tree with 3 leaves each node that isn't a leaf to get the answer.

What's more,there're similar problems in China.

1. http://uoj.ac/problem/130
2. http://tyvj.cn/p/1066 (In Chinese)

Скоро автоматически откроются, в течение часа обычно становятся доступны. 8 тест рандомный, n = 10000, ничего особо не видно

6 1 4 4 4 4 4

Why 38 in this case in D ?

For example,I sum up all ai and incorrectly considered the answer to be "yes" when x-sum=n+1 or n-1,so I am hacked only 9 min after the beginning of the hack phase.

1 4 4 4 4 4

take (1, 4, 4, 4, 4, 4) and spread like this (1, 4, 4) (4, 4) (4) total cost = 21

take (1, 4, 4) and spread (1) (4) (4) total cost 9

take (4, 4) and spread (4) (4) total cost 8

go from top to bottom maintaining DSU for current and previous row

It means pair (x, y) is not the same as pair (y, x).

Btw you can always ask jury a question during the contest, use it if you don't understand something in statement

Oh boy, commenting without knowing codeforces tradition of downvoting.... That's gotta hurt.

For every group of connected stations, it is necessary that every station is reachable from every other station since every pi's are distinct which means that only one train can leave a station(i's are distinct) and only one can reach it(pi's are distinct). Due to which every connected stations would form a cycle and would contribute it's size^2 to the final result.

In this problem, the graph is directed, so if you have a strong component, it is a cycle.

In a cycle, if you can reach vertex Y from vertex X, you can reach vertex X from vertex Y. In other words, all vertex in the same component can reach all other vertex in this component (including itself).

So, if you have a component with N vertex, then you have N * N pairs reachable from each other.

Type cast before you multiply the answer . Like, instead of ans=N*N write ans=(long long)N*N . Do the same for every multiplication hope it will get AC :)

http://mirror.codeforces.com/contest/884

two minutes*