#P7713. 「EZEC-10」打分

「EZEC-10」打分

题目背景

为防止评测机被卡,本题时限为 100 ms。

题目描述

小 A 去参加奥运会。

奥运会中共有 nn 名裁判,分别给小 A 打分 a1,a2,,ana_1,a_2,\ldots,a_n

小 A 对自己的得分不满意,于是他将某名裁判打出的分数加 11,称为一次操作。

但是小 A 不能太贪心,他最多只能进行 mm 次操作。

小 A 的最终得分为:所有得分中,去掉一个最高分和一个最低分后的平均值。

小 A 想知道,他的最终得分最高为多少。

输入格式

第一行两个整数 n,mn,m

第二行 nn 个整数 a1,a2,,ana_1,a_2,\ldots,a_n

输出格式

为了方便输出,小 A 只需知道最终得分×(n2)\times (n-2) 为多少就可以了。

3 2
1 2 3
3
4 3
1 2 2 3
6

提示

【样例 1 解释】

一种可行的方案为:[1,2,3][3,2,3][1,2,3]\to [3,2,3]

【样例 2 解释】

一种可行的方案为:[1,2,2,3][2,3,3,3][1,2,2,3]\to [2,3,3,3]

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(5 points):m=0m=0
  • Subtask 2(10 points):n=3n=3
  • Subtask 3(15 points):n,m103n,m\le 10^3
  • Subtask 4(70 points):无特殊限制。

对于 100%100\% 的数据,3n1053\le n\le 10^50m,ai1090\le m,a_i\le 10^9