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

可复制的 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