Sangbeom's Melancholy
Time limit1sMemory limit128 MB
Given daily moods, compute flower-giving intervals before each depressed run (2T days, or 3T for one chosen longest run) and find the maximum count of distinct covered days by optimally picking which longest run gets the 3T rule.
- Level
Medium7 of 10
- Topics
- Intervals, Greedy, Prefix sum
- Solved
- No attempts yet
Problem
Minkyun has predicted Sangbeom's mood for the next N days.
Each day's mood is represented by an integer. A day with a negative mood is depressed, and a maximal consecutive interval of negative mood values is called a depressed period.
For a depressed period of length T, Minkyun must give flowers from 2T days before the period starts through the day immediately before it starts. For exactly one of the longest depressed periods, the interval starts 3T days before the period starts instead of 2T days before it. If there are several longest depressed periods, only one of them may use the 3T rule; the others use the 2T rule.
Only days among the predicted N days are counted. If a required flower interval begins before the first predicted day, count as many days as are available starting from day 1.
Choose the longest period that uses the 3T rule so that the number of distinct days on which Minkyun gives flowers is maximized. Find that maximum number of days.
Input
The first line contains the number of predicted days N (1 <= N <= 100,000).
The second line contains N integers representing Sangbeom's mood on each day. The absolute value of each mood is at most 100.
Output
Output the maximum number of days on which Minkyun must give flowers.