Informatica Online Judge

  라인 월드 1 [1074 / 0432]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 84   Total Tried : 543


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

[JKJeong 2014]

Background

지학이가 사는 GSHS국은 칠레보다 더 길다.

모든 땅이 직선으로 구성되어 있다. 지학이가 사는 나라의 왕인 seaguy는 지학이가 이번 IamCoder문제를 만드는데 고생이 많았다고, 이 나라 땅의 일부를 선물로 주려고 한다.

지학이가 사는 GSHS국은 N개의 영역이 직선으로 구성되어 있으며, 각 영역은 1000 이하의 가치(각 가치는 0이상이다.)를 가지고 있다.

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

규칙은 직선영역의 땅 중 a번 땅으로부터 b번 땅까지 연속된 영역을 가지고 갈 수 있다.

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

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

Input

첫 번째 줄에 GSHS국의 땅 영역의 개수를 나타내는 정수 N과 지학이가 가져갈 수 총 가치를 나타내는 M값이 공백으로 구분되어 주어진다.

두 번째 줄에는 각 땅의 가치를 나타내는 정수 N개가 공백으로 구분되어 주어진다.

[Sub-task Info]
- 5%의 자료에 대해서는 N이 100 이하의 값이다.
- 15%의 자료에 대해서는 N이 1,000 이하의 값이다.
- 20%의 자료에 대해서는 N이 10,000 이하의 값이다.
- 60%의 자료에 대해서 N이 500,000 이하의 값이다.

Output

지학이는 연속된 영역의 땅의 이익의 최댓값을 출력한다.

IO Example

입력1
5 7
1 2 3 4 5

출력1
6

입력2
6 13
7 1 9 5 2 1

출력2
10

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

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