← 返回题目列表

Codeforces · 2079/D

D. 可爱的后续

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Cute Subsequences - 原题 PDF 第 1 页
原题PDF第9页
可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. First day
                                  Moscow, March 7th, 2025
Problem Diamond. Cute Subsequences

     Input file:         input.txt or standard input
    Output file:       output.txt or standard output
    Time limit:        1 second
    Memory limit:     256 megabytes

You are given an array of n positive integers a1, a2, . . ., an, as well as a positive integer k. You need to
divide the array into k non-empty subsequences such that each element of the array belongs to exactly
one subsequence. A subsequence is a sequence that can be obtained from another sequence by deleting
some elements without changing the order of the remaining elements.

Let the i-th subsequence contain elements with indices j1 < . . . < jl. The value of this subsequence is
defined as the maximum value of ajm + m for all m from 1 to l.

The cost of dividing the array into k subsequences is the sum of the values of these subsequences.

Find the maximum cost of the division.

Input

The first line contains two positive integers n and k (1 ≤k ≤n ≤500 000) — the size of the array and
the number of subsequences to divide it into.
The second line contains n positive integers a1, a2, . . ., an (1 ≤ai ≤109) — the elements of the array.

Output

Output the maximum cost of dividing the given array into k non-empty subsequences.

Example

                  input                                   output
 5 3                                     24
 3 7 10 1 2

Note

In  the sample  test, the  array can be  divided  into  [3, 10],  [7],  [1, 2]. Then the answer  will be
(10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24.

Scoring

The tests for this problem consist of six groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed.


                                      Additional Constraints   Required
                 Group   Points                               Comment
                                                       Groups                                n          k

                      0       0        –          –           –        Examples.

                      1       14     n ≤8        –           0

                      2       19        –        k = 2         –

                      3       17        –          –           –         ai+1 ≤ai

                      4       21        –          –           –       ai+1 ≥ai −1

                      5       15    n ≤1000       –            0, 1

                      6       14        –          –         0 – 5



                                         Page 9 of 9