QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[+12]

# 7837. 挑战积和式

Statistics

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

输入格式

第一行两个正整数 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+5505×6×7=1334

数据范围

对于所有数据: 1kn106,0ai109

  • 子任务 14 分) n,k15
  • 子任务 28 分) n100,k5
  • 子任务 36 分) k=2
  • 子任务 415 分) n100,ai106
  • 子任务 58 分) n100
  • 子任务 67 分) n1000,k10
  • 子任务 78 分) n1000
  • 子任务 89 分) n105,k10
  • 子任务 911 分) n105
  • 子任务 1010 分) k10
  • 子任务 1114 分) 无特殊限制。