Informatica Online Judge

  부동산 사기 [2381 / 094D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 11   Total Tried : 10


The Champion of this Problem (C++) : gs17078 - ms / 467byte
My Best Submission (C++) : N/A

[36th 이다훈(gs17078)]
Writer ID : [gs17078]

Background

민제는 부자가 되고 싶어한다. 그래서 먼저 라인월드의 땅을 사려고 한다.

라인월드는 직선형으로 이루어져 있고 n개의 영역으로 구성되며, 각 영역의 땅 값이 -1,000~1,000 까지의 가치를 지닌다.(1<=n<=30000)

음수는 이 땅을 사면 손해본다는 의미이다. 당연히 값이 클 수록 이익이 큰 땅이다.

이번에는 민제가 최대 k개의 연속된 영역을 얻어갈 수 있다.(단, 1<=k<=300이다.)

즉 민제는 구간 [a1, b1], [a2, b2], ..., [ai, bi]의 i 개의 구간의 땅을 얻을 수 있다.
(단, 1<=i<=k, 1<=a1<=b1
민제가 땅을 적어도 한 구간 이상은 사야한다고 할 때, 민제가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하여 민제를 도와주자.

Input

첫번째 줄에 영역의 크기 n과 가져갈 수 있는 영역의 개수 k가 입력된다.
두번째 줄에는 n개의 각 영역의 가치가 입력된다.

Output

민제가 얻을 수 있는 최대 이익을 출력한다.

IO Example

입력1
5 2
1 2 3 4 5

출력1
15

입력2
7 3
999 -1 999 -2 999 -3 999

출력2
3995

*설명 : 입력 1의 경우에는 1번 땅부터 5번 땅까지 1개의 영역을 얻어가는 것이 가장 이익이다. 입력2의 경우에는 [1,3], [5,5], [7,7]의 3개의 영역을 얻어가는 것이 가장 이익이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]