QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 7837. 挑战积和式

Statistics

给定一个长度为 $ n $ 的自然数序列 $ a $ ,选择一个长度为 $ k $ ,元素均在 $ [1,n] $ 中的正整数序列 $ b $ ,使得 $ \sum_{i=1}^{k}a_{b_i}-\prod_{i=1}^{k}b_i $ 最大。

输入格式

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

第二行 $ n $ 个自然数 $ a_1,a_2,\cdots,a_n $ ,表示序列 $ 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\times 6\times 7=1334 $ 。

数据范围

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

  • 子任务 $ 1 $ ( $ 4 $ 分) $ n,k\leq 15 $ 。
  • 子任务 $ 2 $ ( $ 8 $ 分) $ n\leq 100,k\leq 5 $ 。
  • 子任务 $ 3 $ ( $ 6 $ 分) $ k=2 $ 。
  • 子任务 $ 4 $ ( $ 15 $ 分) $ n\leq 100,a_i\leq 10^6 $ 。
  • 子任务 $ 5 $ ( $ 8 $ 分) $ n\leq 100 $ 。
  • 子任务 $ 6 $ ( $ 7 $ 分) $ n\leq 1000,k\leq 10 $ 。
  • 子任务 $ 7 $ ( $ 8 $ 分) $ n\leq 1000 $ 。
  • 子任务 $ 8 $ ( $ 9 $ 分) $ n\leq 10^5,k\leq 10 $ 。
  • 子任务 $ 9 $ ( $ 11 $ 分) $ n\leq 10^5 $ 。
  • 子任务 $ 10 $ ( $ 10 $ 分) $ k\leq 10 $ 。
  • 子任务 $ 11 $ ( $ 14 $ 分) 无特殊限制。