A173977.互助训练

普及+/提高

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

训练营中有 nn 名学员,按照编号 11 到 nn 排成一列。第 ii 名学员的初始能力值为 aia_i。

教练准备把所有学员划分成若干个小组,并满足以下要求:

  • 每个小组由原队列中连续的学员组成,不能改变学员顺序;
  • 每名学员必须恰好属于一个小组;
  • 每个小组至少有 11 人,至多有 kk 人;
  • 按照小组在原队列中的顺序,任意两个相邻小组的人数必须不同。

当 n≤kn\le k 时,允许所有学员分成一个小组;此时无需检查相邻小组的人数限制。

训练时,同组学员互相帮助。训练结束后,每名学员的能力值都变为其所在小组中所有学员的初始能力值的最大值。

也就是说,如果一个小组由第 ll 名到第 rr 名学员组成,那么该小组训练后的能力值总和为:

(r−l+1)×max⁡(al,al+1,…,ar)(r-l+1)\times\max(a_l,a_{l+1},\ldots,a_r)

不同小组之间不会互相影响。

请你合理划分小组,使所有学员训练后的能力值总和最大,并输出这个最大值。

输入格式

第一行输入两个整数 n,kn,k,分别表示学员数量和每个小组允许的最多人数。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示各学员的初始能力值。

输出格式

输出一个整数,表示所有学员训练后的能力值总和的最大值。

输入输出样例

  • 输入#1

    6 3
    1 7 2 5 10 3

    输出#1

    47
  • 输入#2

    5 5
    1 1 10 1 1

    输出#2

    50

说明/提示

样例解释 1

一种最优划分方案为:

  • 第 1,21,2 名学员组成一组,人数为 22,训练后的能力值总和为 2×7=142\times 7=14;
  • 第 3,4,53,4,5 名学员组成一组,人数为 33,训练后的能力值总和为 3×10=303\times 10=30;
  • 第 66 名学员单独一组,人数为 11,训练后的能力值总和为 1×3=31\times 3=3。

相邻小组的人数分别为 2,3,12,3,1,符合要求,总能力值为 14+30+3=4714+30+3=47。

样例解释 2

将全部 55 名学员分成一个小组,每名学员训练后的能力值都是 1010,总能力值为 5×10=505\times 10=50。

只有一个小组时,不存在需要比较人数的相邻小组。

数据范围

对于所有测试数据,保证:

  • 1≤n≤1051\le n\le 10^5;
  • 2≤k≤1002\le k\le 100;
  • 1≤ai≤1091\le a_i\le 10^9;
  • 不同学员的初始能力值可以相同;
  • kk 可以大于 nn。

输入解题思路,AI测评打分。不知道怎么写?

首页