Zima
레이팅 미적용의견: 0
\(4^{th}\) round, February \(18^{th}\), 2012
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.
In test cases worth 40% of total points, there will be only one winter period with the longest length.
The first line of input contains the integer N (\(1 \le N \le 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.
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.
8
1 -1 4 3 8 -2 3 -3615
1 2 -1 2 3 4 5 6 1 4 8 3 -1 -2 18
First sample description: 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.
Day
1.
2.
3.
4.
5.
6.
7.
8.
Temperature
1
-1
4
3
8
-2
3
-3
Winter
no
yes
no
no
no
yes
no
yes
Winter is coming
yes
no
yes
yes
yes
yes
yes
no평가 및 의견
Zima
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Zima