P16700 [MCO 2026] Team Selection

The dragon Evirir is a competitive flying coach. It trains $N$ dragon athletes, numbered $0, 1, \ldots, N - 1$. For each $i$, athlete $i$ has speed $A_i$. Evirir needs to form a team for an upcoming group flying competition. Due to some strange rules, this team must be a contiguous segment of length at least $K$. That is, Evirir must choose $l$ and $r$ ($0 \le l \le r \le N - 1$) such that $K \le r - l + 1$, and form a team consisting of athletes $l, l+1, \ldots, r$. The strength of a team is defined as the sum of the minimum speed and the maximum speed among the athletes on the team. Please help Evirir find a team with the maximum possible strength. If multiple teams achieve the maximum strength, Evirir prefers the one with the most athletes (because a big team looks more impressive).

The first line contains two integers $N$ and $K$ separated by spaces. The second line contains $N$ integers $A_0, A_1, \ldots, A_{N-1}$ separated by spaces.

Let $m$ be the maximum strength that a team can achieve, and suppose there is a team with strength $m$ consisting of athletes $l, l+1, \ldots, r$. Output three integers separated by spaces: $m$, $l$, and $r$ ($0 \le l \le r \le N - 1$, $K \le r - l + 1$). If there are multiple teams with maximum strength, output any one of them that has the largest possible number of athletes. If you output the correct maximum strength and any valid team, you can still get partial credit. That is, output the correct $m$, and output any integers $l$ and $r$ such that $0 \le l \le r \le N - 1$ and $K \le r - l + 1$. In particular, you can always output $m$, $0$, $K - 1$. For details about scoring, see the Scoring section.

### Hint $\underline{Sample\ 1}$ This sample applies to subtasks 2, 4, 5, and 6. Here there are $N = 9$ athletes, and Evirir must choose a team with at least $K = 3$ athletes. One optimal choice is $l = 2$ and $r = 5$, where the athletes' speeds are $3$, $3$, $4$, and $3$. The minimum speed is $3$ and the maximum speed is $4$, so the team strength is $3 + 4 = 7$. Therefore the output is $\texttt{7 2 5}$. Below are some other outputs and their results. | Output | Score | Explanation | | :---: | :---: | :--- | | `7 7 8` | 0% | This team contains fewer than 3 athletes. | | `4 0 2` | 0% | This team strength is not the maximum possible. | | `7 0 2` | 50% | The team strength is correct, even though the printed team is not correct. | | `7 2 4` | 50% | To get full score, the team size must be as large as possible. | $\underline{Sample\ 2}$ This sample applies to subtasks 2, 3, 4, 5, and 6. Note that outputting $\texttt{4 3 4}$ would also get full score, because this team also achieves the maximum possible strength $4$, and the maximum possible number of athletes is also $2$. $\underline{Sample\ 3}$ This sample applies to subtasks 1, 2, 4, 5, and 6. If the team contains only one athlete, then the team strength is twice that athlete's speed, because both the minimum speed and the maximum speed come from that athlete. ### Scoring For all test cases, the input satisfies the following Constraints: - $1 \le K \le N \le 2 \cdot 10^5$ - For all $0 \le i \le N - 1$, $1 \le A_i \le 10^9$ For all subtasks, if you output the maximum strength and any valid team, you can get 50\% of the score for that subtask. | Subtask | Points | Additional Constraints | | :---: | :---: | :---: | | $1$ | $8$ | $K = 1$ | | $2$ | $10$ | $N \le 5000$ | | $3$ | $14$ | For all $0 \le i \le N - 1$, $A_i \le 2$ | | $4$ | $26$ | For all $0 \le i \le N - 1$, $A_i \le 20$ | | $5$ | $10$ | For all $0 \le i \le N - 1$, $A_i \le 50$ | | $6$ | $32$ | -- | Translated by ChatGPT 5