什么宝宝？

but i think problems are different :)

yes sir in the next contest.

May be system is experiencing some load. Request are getting timed out.

How you know that ?

What the....

If this is true, the contest need to be cancelled definitely. Please announce about the situation and stop wasting competitor's time.

waste a lot of time

Now I have missed my lunch because of this....

good that the contest is unrated.

... The author is innocent ... We shouldn't blame on him. ... Sereja, Thanks for your work and problems.

PS: I wonder on this particular issue, does Codeforces will pay for the problemset? Does the author will write the Editorial as well as it been rated?

No. It's not necessary for n elements to be consecutive!

It is true (at least for me) that CPython 3 is sometimes slower than CPython 2.

I wonder if Codeforces could implement support for PyPy?

I tried Div2 A and B with Go language but both solutions got TLE in pretests. (my solutions: 3675888, 3676731) I feel more optimization is needed for those new languages.

Right, Python 3 is slower than Python 2 in many cases. For example, on my laptop (i7, much faster than judging machines) you solutions work (on the test 11):

• Python 2: 0.65s,
• Python 3: 2s,

Also PyPy works not faster than Python 2:

• PyPy: 1s.

"... so I think something has to be repaired here ..."

I believe Python team should "repair" Python 3 to work faster. On the other hand you should know and understand pros and cons of the language.

Another conclusion that PyPy is not a silver bullet, this problem shows again that it doesn't work faster than CPython 2.

I think you understood the task of problem incorrect, read again, sorry for poor English.

comment deleted

input:

3

1 2 2 2 2

output:

7

Did you figure out how the problem works? I'm interpreting the problem as in a single operation you MUST change the sign of n numbers. In pretest 3, however, the solution would require changing the sign of four numbers while n=3, which I thought would be impossible...

read the constraints again

(It is guaranteed that vi < vi + 1)

solutions are O(n+m)

you might be dont know two pointers :)

show me the code. i think it's O(m+n) solution, not O(m*n), because variable j can not decrease:)

Look at it as the number of multiples in the range [1,n]. Then you get:

n/1 + n/2 + n/3 + ... + n/n

Sum of numbers of divisors for numbers not exceeding N is .

Also, number of divisors of N is o(N^ε) for every ε > 0.

Absolutely! except for the last thing :D

a_i<=1000

Already

div2

The problem tag is dp and math. However, I solve it in a more complicated way — bfs and greedy. First, I use bfs to get all the possible number of multiplying -1. For example, for n = 2, all the possible number are {0,2}. That's to say, I can multiply zero or two numbers in the array by -1. Then, sort the sequence and apply greedy algorithm. If I can make all the numbers positive, then do it. Else I make as more as I can. Be careful of occurrences of 0.

Here's another solution:

If there are any zeros inside the array, then you can ALWAYS make them all positive.

If you have n is an odd number, then you can ALWAYS make them all positive.

If you have n is an even number and there is an even number of negatives, then you can ALWAYS make them all positive. Else, you can ALWAYS make all but one of them positive.

A solution more suitable to a contest, however, is: notice the bound N <= 100 and do BFS on how many negative numbers there could be, since if you change x negative numbers and N-x positive ones in one step, then there will be N-2x more negative numbers (special case: if there's a zero, it's clear that they can all be made non-negative). You don't need to think about all possible cases, just use a simple algorithm to do that for you.

One approach is this (works for any number):

1. Place ? after the first occurrence of the smallest digit in the number.
2. Move ? to the end of the number.
3. If the last digit of the number is 0..8, increase it, remove ? and stop. Otherwise replace ? with ??.
4. So long as the digit before ?? is 9, replace it with 0 and move ?? one step left.
5. If there is another digit before ??, increase it, remove ?? and stop.
6. If there is no digit before ??, replace it with 1 and stop.

For example, the number 6299:

6299, 62?99, 629?9, 6299?, 6299??, 629??0, 62??00, 6300

Just output the following:

??0>>0??
??1>>1??
??2>>2??
??3>>3??
??4>>4??
??5>>5??
??6>>6??
??7>>7??
??8>>8??
??9>>9??
??>>?
0?<>1
1?<>2
2?<>3
3?<>4
4?<>5
5?<>6
6?<>7
7?<>8
8?<>9
9?>>?0
?<>1
0>>??0
1>>??1
2>>??2
3>>??3
4>>??4
5>>??5
6>>??6
7>>??7
8>>??8
9>>??9

The above is composed of five parts: End marker movers of 10 commands, end marker converter of 1 command, converter processes of 10 commands, converter finalization of 1 command, and end marker initializations of 10 commands.

At first, the string doesn't contain any question mark, so some of the end marker initialization commands (d>>??d) is encountered. There will be some double question mark, called end marker, inserted in the string.

Now, some of the end marker mover commands (??d>>d??) will be encountered. This basically moves the end marker one step to the right. As long as this end marker isn't at the end yet, the end marker will be constantly moved, so the end marker will eventually reach the end of the string. At the worst case, the end marker begins in the front of a 25-digit string, taking 25 iterations.

Next, the end marker converter (??>>?) is found, and the end marker becomes a converter sign (?). This converter sign's job is to add the digit exactly before it.

Next, some of the converter process commands (d?<>d) will be encountered, which changes the digit in front of the converter sign. If it's not 9, the addition will not cause any carry, so we're done. Otherwise, the special 9?>>?0 command is encountered, which marks that we need to carry and so we need to add 1 to the previous (more significant) digit. At the worst case, the converter processes need to go all the way to the front with the number 10²⁵ - 1 = 9999999999999999999999999, which takes 25 iterations.

Finally, in the case the converter sign reaches the front of the string, we assume that there is an extra 0 in front of the string, and add 1 to it, hence the special (?<>1) converter finalization command.

This takes 32 commands and at most 53 iterations at the worst case, no matter what the actual numbers are.

To arrive at this solution, first you need to realize that 100 numbers is too much to handle by investigating the numbers; there must be some testcase that causes any submission based on handling numbers to fail. Too many numbers for too few commands. So there should be some easy solution independent of the numbers.

Next you need to figure out that you need to find some way to mark the end of the string (so you can start adding), you need to handle all digits, you need to handle 9s added, and you need to handle 999...9s.

The above is mostly trial-and-error after the above realizations.

There is an editorian on the Russian.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm О(n^2) or http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm O(n^3)

back to 1 (1,1)->(0,1), but get 4 additional bonus (0,1),(0,2),(0,5),(0,7)

I got caught in thinking that too, but it's not true. Consider the following situation:

98
.7
.6
.5
.4
.3
12

where d=1000 and all ai=1000. You should pay 2000 to get out of the rectangle containing 1 and 9, because the gain is 7000.

As a rule of thumb, I would stick to not optimizing anything that doesn't need to be optimized during programming contest. You can improve algorithm after contest.