P9032 [COCI 2022/2023 #1] Neboderi

Domagoj has arrived in the big city of London! Now there is a row of tall skyscrapers in front of him, and he wants to take a photo to remember this moment.

There are $n$ skyscrapers in this row. They can be seen as a sequence $h_1,h_2,\ldots,h_n$, where $h_i$ is the height of the $i$-th building. Domagoj will take a photo of a subarray of these buildings. To better capture the beauty of the city, he wants to photograph at least $k$ skyscrapers. Domagoj has a strange sense of aesthetics: he thinks that having tall skyscrapers in the photo is beautiful; but if the heights of all skyscrapers in the photo have a large common divisor, he thinks it is even more beautiful. If a photo covers the building interval $[l,r]$, and the $\gcd$ of all building heights in this interval is $g$, then Domagoj defines the “beauty value” of this photo as $g \times \sum_{i=l}^r h_i$. Help Domagoj compute the maximum beauty value among all photos he can take.

The first line contains two integers $n,k$, representing the total number of buildings and the minimum number of buildings Domagoj wants to photograph. The second line contains $n$ integers $h_i$, in order, representing the height of each building.

Output one integer in one line, the maximum beauty value.

| Subtask | Points | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $11$ | $n,k \leq 100$ | | $2$ | $22$ | $n,k \leq 5000$ | | $3$ | $27$ | $k \leq 100$ | | $4$ | $18$ | $n,k \leq 5\times 10^4$ | | $5$ | $32$ | No special properties | For $100\%$ of the testdata, $1\leq k \leq n \leq 10^6$ and $1\leq h_i \leq 10^6$. The full score for this problem is $110$ points. Translated by ChatGPT 5