Informatica Online Judge

  라인월드 3 [2354 / 0932]

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


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

[36th 이민준 (gs18081)]
Writer ID : [gs18081]

Background

승민이가 사는 GSHS국은 칠레보다 더 길다.

모든 땅이 직선으로 구성되어 있다. 승민이가 사는 나라의 왕인 seaguy는 승민이가 이번 Turing 발표자료를 만드는데 고생이 많았다고, 이 나라 땅의 일부를 선물로 주려고 한다.

하지만 GSHS국의 국토 중 일부가 황폐화되어, 가지지 않은것보다 더 손해를 보게 되는 땅도 생겼다.

그러한 땅은 음수의 가치를 가지는 것으로 표시된다. 그렇게 모든 땅의 가치는 절대값 1000 이하의 정수로 나타내어진다.

GSHS국의 왕인 seaguy는 승민이에게 가치 M이하의 땅을 다음 규칙에 맞도록 마음껏 가지고 가라고 했다.

규칙은 직선영역의 땅 중 a번 땅으로부터 b번 땅까지 연속된 영역을 가지고 갈 수 있다. 또, 아예 아무런 땅도 가지고 가지 않을 수도 있다. 이 경우에는 이득이 0이 될 것이다.

즉 승민이는 구간 [a, b]의 k개의 연속된 땅을 가지고 갔다면 그 구간의 합 만큼의 이득을 취할 수 있으며 이 때 이득은 M이하여야만 한다.

승민이가 최대한 많은 이익을 볼 수 있도록 도와주자.

Input

첫 번째 줄에 GSHS국의 땅 영역의 개수를 나타내는 정수 N과 승민이가 가져갈 수 총 가치를 나타내는 M값이 공백으로 구분되어 주어진다.
(1<= N <= 200,000 ,0 <= M <= 10^9)
두 번째 줄에는 각 땅의 가치를 나타내는 정수 N개가 공백으로 구분되어 주어진다.
땅의 가치의 절대값은 1,000 미만이다.

[Sub-task Info]
- #1 N이 100 이하의 값이다. (20%)
- #2 N이 10,000 이하의 값이다. (20%)
- #3 추가 제약 조건이 없다. (60%)

Output

승민이가 가져갈 수 있는 연속된 영역의 땅의 이익의 최댓값을 출력한다.

IO Example

입력1
5 6
1 2 3 4 5

출력1
6

입력2
7 10
-4 8 1 -2 7 0 1

출력2
10

* 설명 : 1번의 경우 [1, 3]영역을 가지고 가면 6의 이익을 볼 수 있고, 2번의 경우는 [1, 5]영역을 가지고 가면 모두 10의 이익을 볼 수 있다.

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