「HGOI-1」PMTD

Luogu
IDLGP8480
Time500ms
Memory64MB
DifficultyP1
贪心洛谷原创O2优化洛谷月赛
为了验证 $\text{uuku}$ 学习成果,$\text{bh1234666}$ 给出一个长为 $n$ 整数序列 $a_i$。并让 $\text{uuku}$ 给这个序列进行 $m$ 次操作。 每次操作可以任意选择序列中一个数 $a_i$,令 $a_i$ 变成 $a_i+2$,$a_i-2$,$a_i\times 2$,$\lfloor\frac{a_i}{2}\rfloor$ 这四个结果中的一个。 $\text{bh1234666}$ 希望 $m$ 次操作后,整个序列的极差(最大值减最小值)最大。 显然 $\text{uuku}$ 没有认真学习,所以他希望你来帮他回答这个问题。 ## Input 第一行两个整数 $n$,$m$。 第二行 $n$ 个整数,表示序列 $a_i$。 ## Output 共一行一个整数,表示最大的极差。 [samples] ## Background $\text{uuku}$ 在学习[四则运算](https://baike.baidu.com/item/%E5%9B%9B%E5%88%99%E8%BF%90%E7%AE%97/5337481?fr=aladdin)! ## Note #### 样例解释 第一步操作:将 $1$ 加上 $2$ 得到 $3$。 第二步操作:将 $3$ 乘以 $2$ 得到 $6$。 极差为 $6-0=6$。 #### 数据范围 本题采用**捆绑测试**,共有 $2$ 个 $\text{subtask}$,最终分数为所有 $\text{subtask}$ 分数之和。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \textbf{特殊限制} \cr\hline 1 & 40 & n \le 5,m \le 5 \cr\hline 2 & 60 & \cr\hline \end{array} $$ 对于 $100\%$ 的数据,$2 \le n \le 10^6$,$1 \le m \le 10$,$0 \le a_i \le 10^9$。
Samples
Input #1
3 2
0 1 0 
Output #1
6
API Response (JSON)
{
  "problem": {
    "name": "「HGOI-1」PMTD",
    "description": {
      "content": "为了验证 $\\text{uuku}$ 学习成果,$\\text{bh1234666}$ 给出一个长为 $n$ 整数序列 $a_i$。并让 $\\text{uuku}$ 给这个序列进行 $m$ 次操作。 每次操作可以任意选择序列中一个数 $a_i$,令 $a_i$ 变成 $a_i+2$,$a_i-2$,$a_i\\times 2$,$\\lfloor\\frac{a_i}{2}\\rfloor$ 这四个结果中",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8480"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "为了验证 $\\text{uuku}$ 学习成果,$\\text{bh1234666}$ 给出一个长为 $n$ 整数序列 $a_i$。并让 $\\text{uuku}$ 给这个序列进行 $m$ 次操作。\n\n每次操作可以任意选择序列中一个数 $a_i$,令 $a_i$ 变成 $a_i+2$,$a_i-2$,$a_i\\times 2$,$\\lfloor\\frac{a_i}{2}\\rfloor$ 这四个结果中...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments