시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 66 | 16 | 14 | 22.222% |
As you may know, the frogs are the biggest show-offs of the entire animal kingdom. Some weeks ago, they greatly impressed the other animals by forming a large tower. However, the frog king wants to surpass this performance at the next Benelux Amphibian Pillaring Ceremony (BAPC). He wants the frogs to perform a difficult dance which will end in a climax where all frogs form a tower. You have been appointed choreographer and will practice with the frogs in the following months.
A frog dance is a form of line dance: a certain number of frogs line up and then perform a sequence of jumps, where every jump is either to the left or the right. The frog king decided to make this particular dance more interesting. Firstly, he dictated that the frogs have to increase the length of each jump. This means that for any frog, its first jump will be of length 1, the second of length 2, the third of length 3, and so on. Secondly, the dance should end with all frogs on one big tower. Thirdly, the total number of jumps that the frogs make should be as low as possible, in order to make the dance flashy and impressive-looking.
Since the king is a perfectionist, he wants the dance to be flawless. He has provided you with a team of excellent frog dancers, their starting positions, and the place he wants the frogs to form a tower at the end of the dance. However, the king still isn’t convinced that the dance will be as perfect as he wants it to be, so he visits the rehearsal every day in order to make a change: he might find another frog that is very good at dancing and add it to the line-up, or he might feel that a frog is not good enough and remove him/her. He can even change the position of the final tower if he feels like it.
At the end of every day, the frog king wants to see the dance performed in the most efficient way possible, i.e. with the lowest total number of jumps.
In each case a is between 0 and 106 inclusive. It is guaranteed that the number of times the kings adds or removes a frog is at most 5000.
For each of the C modifications, print one line containing the lowest total number of jumps of the dance after applying the modification.
1 1 0 7 t 0 t 1 t 2 t 3 t 4 t 5 t 6
0 1 3 2 3 5 3
3 0 2 6 6 10 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t 9 t 10
11 6 5 9 4 3 7 9 9 10
0 0 7 t 3 + 4 t 5 + 6 t 2 - 4 t 1
0 1 1 2 6 3 5