Stop Counting!
Time limit7sMemory limit1024 MB
Given a deck of integers, choose one contiguous block to skip so the average of the remaining cards is maximized.
- Level
Hard8 of 10
- Topics
- Math, Prefix sum, Greedy, Binary search
- Solved
- No attempts yet
Problem
The Martingale casino is creating new games to lure in gamblers who tire of the standard fare. Its latest invention is a fast-paced game of chance called Stop Counting!, in which a single customer plays against a dealer with a deck of cards. Each card has some integer value.
The dealer reveals the cards in the deck one by one in order, keeping track of the sum of the played cards and the number of cards shown. Before a card is dealt, the player can call "Stop Counting!" The dealer then continues displaying cards in order but does not include them in the running sums. Before another card is dealt, after calling "Stop Counting!", the player can also call "Start Counting!", and the dealer then includes subsequent cards in the totals. The player can call "Stop Counting!" and "Start Counting!" at most once each, and must call "Stop Counting!" before calling "Start Counting!" A card is counted if it is dealt before the player calls "Stop Counting!" or is dealt after the player calls "Start Counting!"
The payout of the game is the average value of the counted cards. That is, it is the sum of the counted cards divided by the number of counted cards. If no cards are counted, the payout is 0.
You have an in with the dealer and know the full deck in order ahead of time. What is the maximum payout you can achieve?
Input
The first line of the input contains a single integer 1 ≤ N ≤ 1 000 000, the number of cards in the deck.
The second line of the input contains N space-separated integers, the values on the cards. The value of each card is in the range [−109, 109]. The cards are dealt in the same order they are given in the input.
Output
Output the largest attainable payout. The answer is considered correct if the absolute error is less than 10−6 or the relative error is less than 10−9.
Hint
In the first sample, by calling "Stop Counting!" before the −10 and "Start Counting!" before the final 10, we can achieve an average of 10.0 with the counted cards.
In the second sample, all values are negative, so the best strategy is to call "Stop Counting!" before the first card is dealt and "Start Counting!" after the last card is dealt. Since no cards are counted, the average of the counted cards is 0.0.