{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/8cdc5e0ca682abf438608f9eff873c59?v\u003d1715562155\" alt\u003d\"/problems/stopcounting/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eThe Martingale casino is creating new games to lure in new\n gamblers who tire of the standard fare. Their latest invention\n is a fast-paced game of chance called \u003cem\u003eStop Counting!\u003c/em\u003e,\n where a single customer plays with a dealer who has a deck of\n cards. Each card has some integer value.\u003c/p\u003e\n \u003cp\u003eOne by one, the dealer reveals the cards in the deck in\n order, and keeps track of the sum of the played cards and the\n number of cards shown. At some point before a card is dealt,\n the player can call “Stop Counting!” After this, the dealer\n continues displaying cards in order, but does not include them\n in the running sums. At some point after calling “Stop\n Counting!”, and just before another card is dealt, the player\n can also call “Start Counting!” and the dealer then includes\n subsequent cards in the totals. The player can only call “Stop\n Counting!” and “Start Counting!” at most once each, and they\n must call “Stop Counting!” before they can call “Start\n Counting!”. A card is “counted” if it is dealt before the\n player calls “Stop Counting!” or is dealt after the player\n calls “Start Counting!”\u003c/p\u003e\n \u003cp\u003eThe payout of the game is then the average value of the\n counted cards. That is, it is the sum of the counted cards\n divided by the number of counted cards. If there are no counted\n cards, the payout is \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eYou have an ‘in’ with the dealer, and you know the full deck\n in order ahead of time. What is the maximum payout you can\n achieve?\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of the input contains a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq N \\leq 1\\, 000\\,\n 000$\u003c/span\u003e, the number of cards in the deck.\u003c/p\u003e\n \u003cp\u003eThe second line of input contains \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e space-separated integers, the\n values on the cards. The value of each card is in the range\n \u003cspan class\u003d\"tex2jax_process\"\u003e$[-10^{9}, 10^{9}]$\u003c/span\u003e. The\n cards are dealt in the same order they are given in the\n input.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput the largest attainable payout. The answer is\n considered correct if the absolute error is less than\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e, or the relative\n error is less than \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-9}$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample Explanation\u003c/h2\u003e\n \u003cp\u003eIn the first sample, by calling “Stop Counting!” before the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$-10$\u003c/span\u003e and “Start\n Counting!” before the final \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e, we can achieve an average of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10.0$\u003c/span\u003e with the cards that\n are counted.\u003c/p\u003e\n \u003cp\u003eIn the second sample, all values are negative, so the best\n strategy is to call “Stop Counting!” before the first card is\n dealt and call “Start Counting!” after the last card is dealt.\n Since no cards were counted, the average of the counted cards\n is \u003cspan class\u003d\"tex2jax_process\"\u003e$0.0$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n10 10 -10 -4 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10.000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n-3 -1 -4 -1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}