{"problem":{"name":"D. Michael and Charging Stations","description":{"content":"Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs. Michael's day starts from charging his electri","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF853D"},"statements":[{"statement_type":"Markdown","content":"Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs.\n\nMichael's day starts from charging his electric car for getting to the work and back. He spends 1000 burles on charge if he goes to the first job, and 2000 burles if he goes to the second job.\n\nOn a charging station he uses there is a loyalty program that involves bonus cards. Bonus card may have some non-negative amount of bonus burles. Each time customer is going to buy something for the price of _x_ burles, he is allowed to pay an amount of _y_ (0 ≤ _y_ ≤ _x_) burles that does not exceed the bonus card balance with bonus burles. In this case he pays _x_ - _y_ burles with cash, and the balance on the bonus card is decreased by _y_ bonus burles.\n\nIf customer pays whole price with cash (i.e., _y_ = 0) then 10% of price is returned back to the bonus card. This means that bonus card balance increases by bonus burles. Initially the bonus card balance is equal to 0 bonus burles.\n\nMichael has planned next _n_ days and he knows how much does the charge cost on each of those days. Help Michael determine the minimum amount of burles in cash he has to spend with optimal use of bonus card. Assume that Michael is able to cover any part of the price with cash in any day. It is not necessary to spend all bonus burles at the end of the given period.\n\n## Input\n\nThe first line of input contains a single integer _n_ (1 ≤ _n_ ≤ 300 000), the number of days Michael has planned.\n\nNext line contains _n_ integers _a_1, _a_2, ..., _a__n_ (_a__i_ = 1000 or _a__i_ = 2000) with _a__i_ denoting the charging cost at the day _i_.\n\n## Output\n\nOutput the minimum amount of burles Michael has to spend.\n\n[samples]\n\n## Note\n\nIn the first sample case the most optimal way for Michael is to pay for the first two days spending 3000 burles and get 300 bonus burles as return. After that he is able to pay only 700 burles for the third days, covering the rest of the price with bonus burles.\n\nIn the second sample case the most optimal way for Michael is to pay the whole price for the first five days, getting 1000 bonus burles as return and being able to use them on the last day without paying anything in cash.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Michael 刚买了一辆电动汽车用于在城市中通勤。Michael 不喜欢过度劳累，因此每天他只前往两个工作地点中的一个。\n\nMichael 的一天从为电动汽车充电以往返工作地点开始。如果他去第一个工作地点，充电费用为 #cf_span[1000] 卢布；如果去第二个工作地点，则为 #cf_span[2000] 卢布。\n\n他使用的充电站有一个忠诚度计划，涉及积分卡。积分卡上可以有非负数量的积分卢布。每当客户购买价格为 #cf_span[x] 卢布的商品时，他可以选择使用积分卡支付不超过余额的 #cf_span[y] 卢布（#cf_span[0 ≤ y ≤ x]）。此时，他用现金支付 #cf_span[x - y] 卢布，积分卡余额减少 #cf_span[y] 积分卢布。\n\n如果客户完全用现金支付（即 #cf_span[y = 0]），则价格的 10% 将返还至积分卡。这意味着积分卡余额增加 #cf_span[0.1 × x] 积分卢布。初始时，积分卡余额为 0 积分卢布。\n\nMichael 已规划了接下来的 #cf_span[n] 天，并知道每天的充电费用。请帮助 Michael 确定在最优使用积分卡的情况下，他最少需要花费多少现金。假设 Michael 在任何一天都可以用现金支付任意金额。在给定时间段结束时，不需要用完所有积分卢布。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 300 000]），表示 Michael 规划的天数。\n\n下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ai = 1000] 或 #cf_span[ai = 2000]），其中 #cf_span[ai] 表示第 #cf_span[i] 天的充电费用。\n\n请输出 Michael 最少需要花费的现金卢布数。\n\n在第一个样例中，Michael 最优的方式是：前两天完全用现金支付，共花费 3000 卢布，并获得 300 积分卢布返还。之后，他只需为第三天支付 700 卢布现金，其余部分使用积分卢布支付。\n\n在第二个样例中，Michael 最优的方式是：前五天完全用现金支付，获得 1000 积分卢布返还，并在最后一天完全使用这些积分卢布，无需支付任何现金。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 300 000]），表示 Michael 规划的天数。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ai = 1000] 或 #cf_span[ai = 2000]），其中 #cf_span[ai] 表示第 #cf_span[i] 天的充电费用。\n\n## Output\n\n输出 Michael 最少需要花费的现金卢布数。\n\n[samples]\n\n## Note\n\n在第一个样例中，Michael 最优的方式是：前两天完全用现金支付，共花费 3000 卢布，并获得 300 积分卢布返还。之后，他只需为第三天支付 700 卢布现金，其余部分使用积分卢布支付。\n\n在第二个样例中，Michael 最优的方式是：前五天完全用现金支付，获得 1000 积分卢布返还，并在最后一天完全使用这些积分卢布，无需支付任何现金。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 300{,}000 $, be the number of days.\n- Let $ a_i \\in \\{1000, 2000\\} $ for $ i = 1, 2, \\dots, n $, denote the cost of charging on day $ i $.\n- Let $ B \\in \\mathbb{R}_{\\geq 0} $ denote the current bonus card balance (in bonus burles).\n- Initially, $ B = 0 $.\n\n**Payment Rule:**\n\nOn day $ i $, with cost $ a_i $:\n\n- Michael may choose $ y_i \\in [0, a_i] $, such that $ y_i \\leq B $, to pay using bonus burles.\n- Then he pays $ a_i - y_i $ in cash.\n- If $ y_i = 0 $ (i.e., no bonus used), then $ 0.1 \\cdot a_i $ bonus burles are added to the card:  \n  $$\n  B \\leftarrow B + 0.1 \\cdot a_i\n  $$\n- If $ y_i > 0 $, then:  \n  $$\n  B \\leftarrow B - y_i\n  $$\n\n**Objective:**\n\nMinimize total cash spent over $ n $ days:  \n$$\n\\sum_{i=1}^n (a_i - y_i)\n$$\n\n**Constraints:**\n\n- $ 0 \\leq y_i \\leq \\min(B, a_i) $ for all $ i $\n- $ B \\geq 0 $ always\n- $ B $ evolves as described above\n\n**Goal:**  \nFind the minimum possible value of $ \\sum_{i=1}^n (a_i - y_i) $ over all valid sequences $ y_1, y_2, \\dots, y_n $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF853D","tags":["binary search","dp","greedy"],"sample_group":[["3\n1000 2000 1000","3700"],["6\n2000 2000 2000 2000 2000 1000","10000"]],"created_at":"2026-03-03 11:00:39"}}