Informatica Online Judge

  공부에 대한 궤변 [0458 / 01CA]

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


The Champion of this Problem (C++) : gs15120 - 10ms / 1236byte
My Best Submission (C++) : N/A

[]

Background

재호는 자신에게 공부를 시키는 선생님들에게 말대꾸를 하기 위해 다음과 같은 궤변을 준비해 놓았다.
- 공부를 할 때는 ‘피로지수’가 있다. 공부를 시작할 때는 피로지수가 0인데, 공부를 한 시간 하면 피로지수가 1 증가하고, 한 시간 쉬면 피로지수가 1 감소한다. 피로지수가 m을 초과하지 않게만 공부를 할 것이다. 피로지수는 음수로 내려가지 않는다.
이 궤변은 정말 ‘궤변’답지만, 선생님들은 일단 믿어보기로 했다. 대신 매 수업마다 학습량이 다르기 때문에, 선생님들은 재호의 궤변에 맞춰주면서 학습량을 최대화하고 싶어 한다. 어떤 교시에 쉬고 어떤 교시에 공부하는가에 따라서 학습의 총량이 달라질 수 있기 때문이다.
재호의 궤변에 맞춰주면서 학습의 총량을 최대화시킬 때, 그 최대값을 출력하는 프로그램을 작성하시오.

Input

첫 줄에 교시의 n수 , 피로지수의 최대값 m이 주어진다.
다음 n개의 줄에 걸쳐 각 교시의 학습량 pi가 주어진다.
(1<=n<=10,000, 1<=m<=500, 1<=pi<=1,000)

Output

학습의 총량의 최대값을 출력한다.

IO Example

입력
8 2
1
8
2
7
3
6
4
5

출력
27

출처 : 윤형석(서울대 컴퓨터공학과, 2009 IOI 금메달)

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