COCI '22 Contest 1 #5 Neboderi

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 512M

Problem type

Domagoj is in the big city of London! Right now, there is a sequence of tall skyscrapers in front of him and he wants to take a photograph to remember the moment.

The sequence of skyscrapers can be represented as a sequence of n numbers h_1, h_2, \dots, h_n where the number h_i represents the height of the i-th skyscraper. Domagoj will photograph a contiguous subsequence of skyscrapers. To capture more of the city's beauty, he wants to photograph at least k skyscrapers.

Domagoj has a strange sense of beauty of a photograph. He is very happy when there are tall skyscrapers in the photograph, but he is even happier when their heights have a large common divisor! If we label the heights of the contiguous skyscrapers on the photograph with h_l, \dots, h_r, and with g the greatest common divisor of the selected heights, then Domagoj defines the beauty of the photograph as g \cdot (h_l + \dots + h_r).

Help Domagoj determine the beauty of the most beautiful photograph with at least k skyscrapers!

Input Specification

The first line contains two integers n, k (1 \le k \le n \le 10^6), the number of skyscrapers, and the number k.

The second line contains n integers h_1, h_2, \dots, h_n (1 \le h_i \le 10^6), the heights of the skyscrapers, in order.

Output Specification

Print a single line with the required number from the task.


Subtask Points Constraints
1 11 n, k \le 100
2 22 n, k \le 5\,000
3 27 h_i \le 1\,000
4 18 n, k \le 5 \cdot 10^4
5 32 No additional constraints.

Sample Input 1

6 2
2 1 4 4 4 2

Sample Output 1


Explanation for Sample Output 1

Domagoj photographed skyscrapers (4, 4, 4), so the total beauty is 4 \cdot (4 + 4 + 4) = 48.

Sample Input 2

4 1
7 3 9 4

Sample Output 2


Explanation for Sample Output 2

Domagoj photographed only the skyscraper (9), so the total beauty is 9 \cdot 9 = 81.


There are no comments at the moment.