27366번 - Peru 서브태스크다국어언어 제한함수 구현

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 $S_i$. 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 $S_i$ 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: $X_0 · 23^{N−1} + X_1 · 23^{N−2} + \dots + X_{N−1}$ modulo $10^9 + 7$, where $X_i$ represents the minimum total effort to crush the first $i + 1$ beetles.

The contestant must implement the following function:

int solve(int N, int K, int * S);

This function will be called exactly once and must return the result of the above expression modulo $10^9 + 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 $S_i$ represents the strength of beetle $i$).

• $1 ≤ N ≤ 2\,500\,000$
• $1 ≤ K ≤ N$
• $1 ≤ S_i ≤ 2\,000\,000\,000$

• $1 ≤ N ≤ 2\,000$

• $1 ≤ N ≤ 400\,000$

• No additional constraints.

• compile.sh grader.cpp input.txt peru.cpp peru.h ​​​​​​​