19672번 - Feast 다국어

Gug is preparing a feast for his friends. The feast consists of N plates of food arranged in a single row, with the ith plate from the left giving A_i points of satisfaction if eaten. As some plates of food might be rotten, it is possible that A_i is negative.

There are a total of K people involved in the feast, and each person will be assigned a consecutive segment of plates to consume. This segment can possibly be empty. The segments of two people cannot overlap, as food cannot be eaten twice. Gug wishes to assign the plates to his friends such that the sum of satisfaction points of all the plates of food consumed is maximised.

Your program must read from standard input.

The input starts with a line with two integers N and K.

The next line will contain N integers A₁, . . . , A_N.

Your program must print to standard output.

The output should contain a single integer on a single line, the sum of satisfaction points in an optimal assignment.

• 1 ≤ K ≤ N ≤ 3 × 10⁵
• 0 ≤ |A_i| ≤ 10⁹