시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 1024 MB 0 0 0 0.000%

문제

Syrup the Turtle often swims in a pond next to his house. Having been carved out by glacial movements long ago, the pond is narrow and straight — shaped almost like a river, but with waters calm and still enough to allow a turtle to swim both ways unimpeded.

Today, Syrup was in the pond as usual when he caught a glance of the dreaded green speck — a blooming algal spore. After bouts of heavy rain, the rich soil washed into the pond gradually disintegrates and provides the nutrition for the normally benign local algae to grow at a massively accelerated rate. If left unchecked, these blooms could expand to the point where they block out sunlight from reaching the lake-bed plants below; setting the stage for ecological imbalances which could mar the water for months on end.

Fortunately, Syrup is no stranger to this game and has a simple but effective answer to this infrequent problem — eating it. He has identified N soil runoff points in the linear pond where algae is starting to bloom, which can be numbered from one end to the other as 1 through N. The ith and (i + 1)th points are separated by a distance of Di metres, and Syrup is currently at the Kth spot alongside the spore he first noticed. He will now swallow down that very spore, before swimming off in one of the two directions at a speed of 1 metre per second and eating up every cluster of algae he passes until all blooms are gone.

Each of the N runoff points starts off with 0 algal strands, and will gain 1 strand every second until Syrup reaches it. Turtles are robust and Syrup has no difficulty eating any number of algal strands. However, as overgrown algae tastes no good, he would prefer to minimise the number of strands eaten over his trip. Your task is to find the fewest number of total algae strands Syrup has to eat to clear the pond of algae, given that he takes the best route along it.

입력

Your program must read from standard input.

The first line contains two integers, N and K.

The second line contains N − 1 integers. The ith integer represents Di, the distance in metres between runoff points i and i + 1.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the minimum possible total algal strands Syrup must eat to remove all the algae from the pond.

제한

  • 2 ≤ N ≤ 3 × 105
  • 1 ≤ K ≤ N
  • 1 ≤ Di ≤ 106

서브태스크

번호 배점 제한
1 7

N ≤ 100

2 11

N ≤ 2000

3 10

1 ≤ K ≤ min(N, 20)

4 6

Di = 1

5 12

1 ≤ K ≤ min(N, 2000), Di ≥ Di+1 for all i ≠ 0 (mod 100)

6 25

1 ≤ K ≤ min(N, 2000)

7 29

예제 입력 1

7 3
5 2 4 2 2 5

예제 출력 1

86

The optimal route is to swim between the points in the order 3 −→ 2 −→ 4 −→ 5 −→ 6 −→ 7 −→ 1, for a total of 0 + 2 + 8 + 10 + 12 + 17 + 37 = 86 algal strands eaten.

예제 입력 2

9 5
4 3 2 1 1 3 6 10

예제 출력 2

129

The optimal route is to swim between the points in the order 5 −→ 6 −→ 4 −→ 3 −→ 2 −→ 1 −→ 7 −→ 8 −→ 9, for a total of 0 + 1 + 3 + 5 + 8 + 12 + 26 + 32 + 42 = 129 algal strands eaten.

예제 입력 3

6 4
1 1 1 1 1

예제 출력 3

21

One optimal route is to swim between the points in the order 4 −→ 3 −→ 2 −→ 1 −→ 5 −→ 6, for a total of 0 + 1 + 2 + 3 + 7 + 8 = 21 algal strands eaten.

채점 및 기타 정보

  • 예제는 채점하지 않는다.