P8102 "LCOI2022" Cow Insertion

Farmer John has welcomed a new cow, Bessie. Each cow has a certain happiness value, and Farmer John hopes that Bessie can live a happier life here.

There are originally $n$ cows in the barn, with a happiness influence distance of $m$. Let $a_i$ denote the happiness value of the $i(1\le i\le n)$-th cow in the original barn. Bessie also has a happiness value $A$. The total happiness of the whole barn is defined as $\sum\limits_{i=1}^{n-m+1}\ \max\limits_{i\le j\le i+m-1}\ a_j$. Bessie can be placed between any two cows, or at the beginning or the end. Farmer John wants to know: after Bessie comes here, what is the maximum possible total happiness of the whole barn.

The first line contains three integers $n,m,A$, representing the number of cows, the happiness influence distance, and Bessie's happiness value. The next line contains $n$ numbers $a_i$, representing the happiness value of the $i(1\le i\le n)$-th cow in the original barn.

Output a single line representing the maximum total happiness of the whole barn after Bessie comes here.

[Sample Explanation] - When Bessie is in the first position ($50,60,100,70$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{60,100}+\max\cases{100,70}$, i.e., $60+100+100=260$. - When Bessie is in the second position ($60,50,100,70$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,50}+\max\cases{50,100}+\max\cases{100,70}$, i.e., $60+100+100=260$. - When Bessie is in the third position ($60,100,50,70$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,50}+\max\cases{50,70}$, i.e., $100+100+70=270$. - When Bessie is in the fourth position ($60,100,70,50$), the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{60,100}+\max\cases{100,70}+\max\cases{70,50}$, i.e., $70+100+100=270$. Clearly, the maximum total happiness of the whole barn is $\newcommand{\cases}[1]{\{#1\}}\max\cases{260,260,270,270}=270$. [Constraints and Notes] |subtask|$n\le$|points| |:-:|:-:|:-:| |$1$|$5\times10^2$|$10$| |$2$|$5\times10^3$|$20$| |$3$|$5\times10^6$|$70$| For $100\%$ of the testdata, $1\le m\le n$, and $0\le a_i, A\le100$. Translated by ChatGPT 5