{"problem":{"name":"A. Planning","description":{"content":"Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are _n_ flights that must depart today, the _i_\\-th of them is planned to depart at the _i_\\-th minute of","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF853A"},"statements":[{"statement_type":"Markdown","content":"Helen works in Metropolis airport. She is responsible for creating a departure schedule. There are _n_ flights that must depart today, the _i_\\-th of them is planned to depart at the _i_\\-th minute of the day.\n\nMetropolis airport is the main transport hub of Metropolia, so it is difficult to keep the schedule intact. This is exactly the case today: because of technical issues, no flights were able to depart during the first _k_ minutes of the day, so now the new departure schedule must be created.\n\nAll _n_ scheduled flights must now depart at different minutes between (_k_ + 1)\\-th and (_k_ + _n_)\\-th, inclusive. However, it's not mandatory for the flights to depart in the same order they were initially scheduled to do so — their order in the new schedule can be different. There is only one restriction: no flight is allowed to depart earlier than it was supposed to depart in the initial schedule.\n\nHelen knows that each minute of delay of the _i_\\-th flight costs airport _c__i_ burles. Help her find the order for flights to depart in the new schedule that minimizes the total cost for the airport.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 300 000), here _n_ is the number of flights, and _k_ is the number of minutes in the beginning of the day that the flights did not depart.\n\nThe second line contains _n_ integers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ 107), here _c__i_ is the cost of delaying the _i_\\-th flight for one minute.\n\n## Output\n\nThe first line must contain the minimum possible total cost of delaying the flights.\n\nThe second line must contain _n_ different integers _t_1, _t_2, ..., _t__n_ (_k_ + 1 ≤ _t__i_ ≤ _k_ + _n_), here _t__i_ is the minute when the _i_\\-th flight must depart. If there are several optimal schedules, print any of them.\n\n[samples]\n\n## Note\n\nLet us consider sample test. If Helen just moves all flights 2 minutes later preserving the order, the total cost of delaying the flights would be (3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38 burles.\n\nHowever, the better schedule is shown in the sample answer, its cost is (3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20 burles.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Helen 在 Metropolis 机场工作，负责制定航班离港时间表。今天共有 #cf_span[n] 个航班必须起飞，第 #cf_span[i] 个航班原计划在当天第 #cf_span[i] 分钟起飞。\n\n由于 Metropolis 机场是 Metropolia 的主要交通枢纽，维持时刻表十分困难。今天正是如此：由于技术问题，当天前 #cf_span[k] 分钟内没有航班起飞，因此必须重新制定离港时间表。\n\n现在，所有 #cf_span[n] 个航班必须在第 #cf_span[(k + 1)] 分钟到第 #cf_span[(k + n)] 分钟（含）之间，选择不同的分钟起飞。然而，航班的起飞顺序可以与原计划不同——新时间表中的顺序可以调整。唯一的限制是：任何航班不得早于其原计划的起飞时间起飞。\n\nHelen 知道，第 #cf_span[i] 个航班每延误一分钟，机场将损失 #cf_span[ci] 布尔。请帮助她确定新时间表中的航班起飞顺序，使得机场的总延误成本最小。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 300 000]），其中 #cf_span[n] 是航班数量，#cf_span[k] 是当天开始时航班未能起飞的分钟数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 107]），其中 #cf_span[ci] 表示第 #cf_span[i] 个航班每延误一分钟的成本。\n\n第一行必须输出航班延误的最小可能总成本。\n\n第二行必须输出 #cf_span[n] 个互不相同的整数 #cf_span[t1, t2, ..., tn]（#cf_span[k + 1 ≤ ti ≤ k + n]），其中 #cf_span[ti] 表示第 #cf_span[i] 个航班的起飞分钟。如果有多个最优方案，输出任意一个即可。\n\n考虑样例测试：如果 Helen 将所有航班整体推迟 2 分钟并保持原有顺序，则总延误成本为 #cf_span[(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38] 布尔。\n\n然而，样例答案中展示的更好方案的成本为 #cf_span[(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20] 布尔。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 300 000]），其中 #cf_span[n] 是航班数量，#cf_span[k] 是当天开始时航班未能起飞的分钟数。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 107]），其中 #cf_span[ci] 表示第 #cf_span[i] 个航班每延误一分钟的成本。\n\n## Output\n\n第一行必须输出航班延误的最小可能总成本。第二行必须输出 #cf_span[n] 个互不相同的整数 #cf_span[t1, t2, ..., tn]（#cf_span[k + 1 ≤ ti ≤ k + n]），其中 #cf_span[ti] 表示第 #cf_span[i] 个航班的起飞分钟。如果有多个最优方案，输出任意一个即可。\n\n[samples]\n\n## Note\n\n考虑样例测试：如果 Helen 将所有航班整体推迟 2 分钟并保持原有顺序，则总延误成本为 #cf_span[(3 - 1)·4 + (4 - 2)·2 + (5 - 3)·1 + (6 - 4)·10 + (7 - 5)·2 = 38] 布尔。然而，样例答案中展示的更好方案的成本为 #cf_span[(3 - 1)·4 + (6 - 2)·2 + (7 - 3)·1 + (4 - 4)·10 + (5 - 5)·2 = 20] 布尔。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ n $ be the number of flights.\n- Let $ k $ be the number of initial minutes during which no flights could depart.\n- Let $ c_i $ be the cost per minute of delay for flight $ i $, for $ i = 1, 2, \\dots, n $.\n- The original departure time of flight $ i $ is $ i $ (i.e., flight $ i $ was scheduled to depart at minute $ i $).\n- The new departure times must be distinct integers in the range $ [k+1, k+n] $.\n- Flight $ i $ cannot depart earlier than its original scheduled time $ i $: $ t_i \\geq i $.\n- The delay of flight $ i $ is $ t_i - i $, and its cost is $ c_i \\cdot (t_i - i) $.\n\n**Constraints:**\n\n- $ t_i \\in \\{k+1, k+2, \\dots, k+n\\} $, all $ t_i $ distinct.\n- $ t_i \\geq i $ for all $ i \\in \\{1, 2, \\dots, n\\} $.\n\n**Objective:**\n\nMinimize total cost:  \n$$\n\\sum_{i=1}^{n} c_i \\cdot (t_i - i)\n$$\n\nEquivalently, minimize:  \n$$\n\\sum_{i=1}^{n} c_i \\cdot t_i - \\sum_{i=1}^{n} c_i \\cdot i\n$$\n\nSince $ \\sum_{i=1}^{n} c_i \\cdot i $ is constant, minimizing $ \\sum_{i=1}^{n} c_i \\cdot t_i $ is equivalent.\n\nThus, the problem reduces to:  \n**Assign distinct times $ t_i \\in [k+1, k+n] $ to flights $ i $, subject to $ t_i \\geq i $, to minimize $ \\sum_{i=1}^{n} c_i t_i $.**\n\n---\n\n**Optimal Strategy (Greedy):**\n\nTo minimize $ \\sum c_i t_i $, assign the **smallest available time slots** to the flights with the **largest $ c_i $** (since higher cost per minute should be penalized less by assigning earlier times).\n\nHowever, each flight $ i $ has a **minimum allowed departure time** $ \\max(i, k+1) $.\n\nThus, we can use a **greedy algorithm with a priority queue**:\n\n1. Consider time slots from $ k+1 $ to $ k+n $ in order.\n2. For each time slot $ t $, consider all flights $ i $ such that $ i \\leq t $ (i.e., flights eligible to depart at or before $ t $).\n3. Among all eligible flights not yet assigned, pick the one with the **maximum $ c_i $** and assign it to time $ t $.\n4. Use a max-heap (priority queue) to efficiently select the flight with highest cost among those eligible at each step.\n\n---\n\n**Formal Algorithm:**\n\nLet $ \\text{heap} $ be a max-heap (priority queue) of pairs $ (c_i, i) $, keyed by $ c_i $.\n\nInitialize:\n- $ \\text{heap} = \\emptyset $\n- $ j = 1 $ (index of next flight to consider for eligibility)\n- $ \\text{result}[1..n] $: array to store assigned departure times\n\nFor $ t = k+1 $ to $ k+n $:\n\n1. While $ j \\leq n $ and $ j \\leq t $:  \n   Push $ (c_j, j) $ into heap.  \n   Increment $ j $.\n\n2. Pop the flight $ i $ with maximum $ c_i $ from heap.\n\n3. Assign $ t_i = t $.\n\n4. Record $ t_i $ for flight $ i $.\n\nAfter processing all $ t $, compute total cost:  \n$$\n\\sum_{i=1}^{n} c_i \\cdot (t_i - i)\n$$\n\nOutput:\n- First line: total cost\n- Second line: $ t_1, t_2, \\dots, t_n $ (in original flight order)\n\n---\n\n**Final Formal Statement:**\n\nLet $ \\mathcal{T} = \\{k+1, k+2, \\dots, k+n\\} $.  \nFind a bijection $ t: \\{1,\\dots,n\\} \\to \\mathcal{T} $ such that:\n\n- $ t(i) \\geq i $ for all $ i \\in \\{1,\\dots,n\\} $,  \n- and $ \\sum_{i=1}^n c_i \\cdot t(i) $ is minimized.\n\nThis is achieved by the greedy algorithm above:  \nAt each time slot $ t \\in \\mathcal{T} $, assign the unassigned flight $ i $ with $ i \\leq t $ and maximum $ c_i $ to $ t $.\n\n**Output:**\n- Minimum total cost: $ \\sum_{i=1}^n c_i (t_i - i) $\n- Schedule: $ t_1, t_2, \\dots, t_n $ (in flight index order)","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF853A","tags":["greedy"],"sample_group":[["5 2\n4 2 1 10 2","20\n3 6 7 4 5"]],"created_at":"2026-03-03 11:00:39"}}