第 2 题可爱的子序列 (`cutesubsequences`)

CSP-S 复赛模拟赛 23 · 时间限制 1 s · 空间限制 256 MB · 86 个测试点 · 特殊 Judge

本题使用文件输入输出：输入文件 cutesubsequences.in，输出文件 cutesubsequences.out。

题目描述

给定一个由 $n$ 个正整数组成的数组 $a_1, a_2, \ldots, a_n$ ，以及一个正整数 $k$ 。你需要把该数组划分成 $k$ 个非空子序列，使得数组中的每个元素恰好属于一个子序列。子序列是指从另一个序列中删去某些元素、不改变剩余元素顺序后得到的序列。

设第 $i$ 个子序列包含下标为 $j_1 < \ldots < j_l$ 的元素。该子序列的值定义为对所有 $m$ （1 到 $l$ ）而言 $a_{j_m} + m$ 的最大值。

把数组划分成 $k$ 个子序列的代价是这些子序列的值之和。

求该划分的最大代价。

第一行包含两个正整数 $n$ 和 $k$ （ $1 \le k \le n \le 500\,000$ ）——数组的大小，以及要划分成的子序列个数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le 10^9$ ）——数组的元素。

输出把给定数组划分成 $k$ 个非空子序列的最大代价。

输入：

5 3
3 7 10 1 2

输出：

在样例中，可以把数组划分成 $[3, 10]$ 、 $[7]$ 、 $[1, 2]$ 。此时答案为 $(10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24$ 。

本题的测试点分为六组。只有当该组的所有测试点以及所有所需组的测试点都通过时，该组的分数才会被计入。