COCI '11 Contest 4 #2 Zima

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

In the old times, when dragons ruled the land, air temperature never fell below zero degrees. But after dragons left, nice and warm times went with them.

We say that day is a winter day when average temperature for that day is below zero. We say that T consecutive winter days form a winter period of length T.

There are some people that annoy everyone by rambling on about some winter that is coming. So a law had to be made, stating that you are allowed to say that winter is coming at most 2T days before a winter period of length T. Exception to this is only the winter period with the longest length, that can be announced at most 3T days before it begins. During some winter period, you can't say that this period is coming, since it's already here, but you can announce future winter periods according to the rules above. If there are more than one winter periods with the longest length, then only one is chosen and 3T days rule is applied only to that period.

Knowing expected temperatures for some time period, find out the maximum number of days during which it is allowed to say that winter is coming.

Input Specification

The first line of input contains the integer N (1 \leq N \leq 100\,000), length of the overall time period we are considering. The following line contains N integers, temperatures of consecutive days in considered period. Absolute values of these integers won't exceed 100.

Output Specification

The first and only line of output should contain the maximum number of days during which it is allowed to announce the winter is coming.

Scoring

In test cases worth 40\% of total points, there will be only one winter period with the longest length.

Sample Input 1

8
1 -1 4 3 8 -2 3 -3

Sample Output 1

6

Explanation for Sample Output 1

There are three winter periods of length one. In order to obtain the requested maximum, best thing to do is to choose the second one to apply the 3T days rule, and starting announcing it three days before it arrives.

Day12345678
Temperature1-1438-23-3
Winternoyesnononoyesnoyes
Winter is comingyesnoyesyesyesyesyesno

Sample Input 2

15
1 2 -1 2 3 4 5 6 1 4 8 3 -1 -2 1

Sample Output 2

8

Comments

There are no comments at the moment.