{"problem":{"name":"B. Cormen — The Best Friend Of a Man","description":{"content":"Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk. Empirically Polycarp learned that the dog needs at le","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF732B"},"statements":[{"statement_type":"Markdown","content":"Recently a dog was bought for Polycarp. The dog's name is Cormen. Now Polycarp has a lot of troubles. For example, Cormen likes going for a walk.\n\nEmpirically Polycarp learned that the dog needs at least _k_ walks for any two consecutive days in order to feel good. For example, if _k_ = 5 and yesterday Polycarp went for a walk with Cormen 2 times, today he has to go for a walk at least 3 times.\n\nPolycarp analysed all his affairs over the next _n_ days and made a sequence of _n_ integers _a_1, _a_2, ..., _a__n_, where _a__i_ is the number of times Polycarp will walk with the dog on the _i_\\-th day while doing all his affairs (for example, he has to go to a shop, throw out the trash, etc.).\n\nHelp Polycarp determine the minimum number of walks he needs to do additionaly in the next _n_ days so that Cormen will feel good during all the _n_ days. You can assume that on the day before the first day and on the day after the _n_\\-th day Polycarp will go for a walk with Cormen exactly _k_ times.\n\nWrite a program that will find the minumum number of additional walks and the appropriate schedule — the sequence of integers _b_1, _b_2, ..., _b__n_ (_b__i_ ≥ _a__i_), where _b__i_ means the total number of walks with the dog on the _i_\\-th day.\n\n## Input\n\nThe first line contains two integers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 500) — the number of days and the minimum number of walks with Cormen for any two consecutive days.\n\nThe second line contains integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 500) — the number of walks with Cormen on the _i_\\-th day which Polycarp has already planned.\n\n## Output\n\nIn the first line print the smallest number of additional walks that Polycarp should do during the next _n_ days so that Cormen will feel good during all days.\n\nIn the second line print _n_ integers _b_1, _b_2, ..., _b__n_, where _b__i_ — the total number of walks on the _i_\\-th day according to the found solutions (_a__i_ ≤ _b__i_ for all _i_ from 1 to _n_). If there are multiple solutions, print any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"最近，Polycarp 买了一只狗，名字叫 Cormen。现在 Polycarp 遇到了很多麻烦，比如 Cormen 喜欢出去散步。\n\n通过经验，Polycarp 发现，为了使狗感到舒服，任意连续两天的散步次数之和至少为 #cf_span[k]。例如，如果 #cf_span[k = 5]，而昨天 Polycarp 与 Cormen 散步了 #cf_span[2] 次，那么今天他至少需要散步 #cf_span[3] 次。\n\nPolycarp 分析了接下来的 #cf_span[n] 天的所有事务，并生成了一个包含 #cf_span[n] 个整数的序列 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示 Polycarp 在第 #cf_span[i] 天因处理事务（例如去商店、扔垃圾等）而计划与狗散步的次数。\n\n请帮助 Polycarp 确定在接下来的 #cf_span[n] 天中，他至少需要额外增加多少次散步，才能让 Cormen 在这 #cf_span[n] 天中每天都感到舒服。你可以假设，在第一天之前和第 #cf_span[n] 天之后，Polycarp 都会与 Cormen 散步恰好 #cf_span[k] 次。\n\n编写一个程序，找出最少的额外散步次数以及对应的计划——一个整数序列 #cf_span[b1, b2, ..., bn]（#cf_span[bi ≥ ai]），其中 #cf_span[bi] 表示第 #cf_span[i] 天与狗散步的总次数。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 500]）——天数和任意连续两天中与 Cormen 散步的最小次数。第二行包含整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 500]）——Polycarp 已计划的第 #cf_span[i] 天与 Cormen 散步的次数。\n\n## Output\n\n第一行输出 Polycarp 在接下来的 #cf_span[n] 天中为让 Cormen 感到舒服而必须增加的最少散步次数。第二行输出 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn]，其中 #cf_span[bi] 表示根据所求解法第 #cf_span[i] 天的散步总次数（对所有 #cf_span[i] 从 1 到 #cf_span[n]，满足 #cf_span[ai ≤ bi]）。如果有多个解，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 500 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers with $ 0 \\leq a_i \\leq 500 $.  \nLet $ b_0 = k $, $ b_{n+1} = k $ (virtual days before and after).  \n\n**Constraints**  \nFor each $ i \\in \\{1, \\dots, n\\} $:  \n- $ b_i \\geq a_i $  \n- $ b_i + b_{i-1} \\geq k $  \n- $ b_i + b_{i+1} \\geq k $  \n\n**Objective**  \nMinimize $ \\sum_{i=1}^n (b_i - a_i) $, and output the minimal total additional walks and a sequence $ B = (b_1, \\dots, b_n) $ achieving it.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF732B","tags":["dp","greedy"],"sample_group":[["3 5\n2 0 1","4\n2 3 2"],["3 1\n0 0 0","1\n0 1 0"],["4 6\n2 4 3 5","0\n2 4 3 5"]],"created_at":"2026-03-03 11:00:39"}}