#2144. Peru
Peru
Peru
题目描述
RMI 2020, Day 1 Online, 3.12.2020 Problem Peru C header: peru.h C++ header: peru.h This morning, Roxy found N beetles on her desk. These beetles are numbered from 0 to N −1 and each beetle i has a strength Si. Roxy wants to crush the beetles so she can do her math homework. In order to do this, she bought a special glove which she can use to hit a contiguous subsequence of K beetles. If Roxy makes an effort E, then those beetles whose strength Si is smaller than or equal to E will be crushed, while all others will remain unharmed. The crushed beetles maintain their positions on the desk. Roxy can use the glove as many times as she wants. Roxy wants to know if you can compute the minimum total effort needed to crush the first i beetles for each 1 ≤i ≤N. Because there are too many numbers, Roxy agreed you should give her the result of the following expression: X0 · 23N−1 + X1 · 23N−2 + . . . + XN−1 modulo 109 + 7, where Xi represents the minimum total effort to crush the first i + 1 beetles. Implementation details The contestant must implement the following function: int ∗S ) ; int solve ( int N, int K, This function will be called exactly once and must return the result of the above expression modulo 109 + 7. The parameters of this function are N (the number of beetles), K (the length of the contiguous subsequences she can hit with the glove) and S (an array of length N, where Si represents the strength of beetle i). Constraints • 1 ≤N ≤2 500 000 • 1 ≤K ≤N • 1 ≤Si ≤2 000 000 000 Subtask 1 (18 points) • 1 ≤N ≤2 000 Subtask 2 (31 points) • 1 ≤N ≤400 000 Subtask 3 (51 points) • No additional constraints. Example input output 8 3 720026253 3 2 9 8 7 11 3 4 The array X is {3, 3, 9, 12, 12, 20, 23, 23}. 1
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
8 3
3 2 9 8 7 11 3 4
720026253