#PQJ1431x7837. QOJ 1431_7837

    ID: 2606 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测枚举

QOJ 1431_7837

标题: 挑战积和式 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

给定一个长度为 n 的自然数序列 a ,选择一个长度为 k ,元素均在 [1,n] 中的正整数序列 b ,使得 ∑i=1kabi−∏i=1kbi 最大。

输入格式

第一行两个正整数 n,k ,表示序列 a 的长度和序列 b 的长度。

第二行 n 个自然数 a1,a2,⋯,an ,表示序列 a 。

输出格式

仅一行一个自然数,表示答案。

样例输入 1

10 3
185 327 366 422 478 516 550 567 560 583

样例输出 1

1334

样例 1 解释

当 b=[5,6,7] 时,取到最大值 478+516+550−5×6×7=1334 。

数据范围

对于所有数据: 1≤k,n≤106,0≤ai≤109 。

  • 子任务 1 ( 4 分) n,k≤15 。
  • 子任务 2 ( 8 分) n≤100,k≤5 。
  • 子任务 3 ( 6 分) k=2 。
  • 子任务 4 ( 15 分) n≤100,ai≤106 。
  • 子任务 5 ( 8 分) n≤100 。
  • 子任务 6 ( 7 分) n≤1000,k≤10 。
  • 子任务 7 ( 8 分) n≤1000 。
  • 子任务 8 ( 9 分) n≤105,k≤10 。
  • 子任务 9 ( 11 分) n≤105 。
  • 子任务 10 ( 10 分) k≤10 。
  • 子任务 11 ( 14 分) 无特殊限制。