#P12566. [集训队互测 2024day11]挑战积和式

    ID: 11729 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000动态规划数学分治斜率优化单调队列多项式贪心

[集训队互测 2024day11]挑战积和式

给定一个长度为 nn 的自然数序列 aa ,选择一个长度为 kk ,元素均在 [1,n][1,n] 中的正整数序列 bb ,使得 ∑i=1kabi−∏i=1kbi\sum_{i=1}^{k}a_{b_i}-\prod_{i=1}^{k}b_i 最大。

输入格式

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

第二行 nn 个自然数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n ,表示序列 aa 。

输出格式

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

样例输入 1

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

样例输出 1

1334

样例 1 解释

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

数据范围

对于所有数据: 1≤k,n≤106,0≤ai≤1091\leq k, n\leq 10^6,0\leq a_i\leq 10^9 。

  • 子任务 11 ( 44 分) n,k≤15n,k\leq 15 。
  • 子任务 22 ( 88 分) n≤100,k≤5n\leq 100,k\leq 5 。
  • 子任务 33 ( 66 分) k=2k=2 。
  • 子任务 44 ( 1515 分) n≤100,ai≤106n\leq 100,a_i\leq 10^6 。
  • 子任务 55 ( 88 分) n≤100n\leq 100 。
  • 子任务 66 ( 77 分) n≤1000,k≤10n\leq 1000,k\leq 10 。
  • 子任务 77 ( 88 分) n≤1000n\leq 1000 。
  • 子任务 88 ( 99 分) n≤105,k≤10n\leq 10^5,k\leq 10 。
  • 子任务 99 ( 1111 分) n≤105n\leq 10^5 。
  • 子任务 1010 ( 1010 分) k≤10k\leq 10 。
  • 子任务 1111 ( 1414 分) 无特殊限制。