시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 512 MB | 92 | 35 | 32 | 38.095% |
Nick is a bird watcher and often visits the forum “CrowFinders” to discuss his hobby with like-minded people. CrowFinders has a voting system where users can upvote or downvote comments, which increases or decreases their score by 1. This means that each comment can end up with any integer score (including negative scores). Once when Nick was browsing a heated discussion about the classification of jackdaws as crows, he found something very pleasing: a chain of comments that alternated between positive and negative scores. But a few days later, he found that the comment chain was no longer alternating. Now Nick wants to make it alternating again.
A comment chain is alternating if the scores s1, s2, . . . , sn of the comments all are non-zero, and every pair of adjacent scores si, si+1 have opposite signs. In particular, a single comment with a non-zero score or even a comment chain without any comment is an alternating comment chain.
There are two operations Nick can do to make the comment chain alternating:
Nick can apply these operations in any order, any number of times. How fast can he make the comment chain alternating?
For example, consider Sample Input 1 below, where the scores in the comment chain are 8, 8, 2, −2, and it takes Nick 10 seconds to create an account and 50 seconds to file a report for one comment. In this case it is optimal to first create 3 fake accounts and use them to upvote the fourth comment and downvote the third, followed by reporting the first comment. This results in the scores 8, −1, 1, which is an alternating chain. The time used for this is 80 seconds.
The input consists of:
Output the smallest time to make the comment chain alternating by applying the operations above.
4 10 50 8 8 2 -2
80
6 100 33 5 -13 0 0 -12 0
132
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2019 J번