세 조각

면접 대비

시간 제한1초메모리 제한1024 MB

요약

배열에서 길이가 M인 연속한 세 구간을 고르고, 각 구간의 합이 K 이하가 되는 가장 큰 M을 구합니다.

문제

양의 정수 $N$ 개로 이루어진 배열 $A_{0}, A_{1}, A_{2}, \ldots, A_{N-1}$ 이 주어진다. 또 양의 정수 $K$ 가 주어진다. 다음 조건을 만족하는 가장 큰 양의 정수 $M$ 을 구하라.

다음을 만족하는 정수 $0 \le i \le N-3M$ 이 존재한다.
1. $\sum_{j=i}^{i+M-1}A_{j} \le K$
2. $\sum_{j=i+M}^{i+2M-1}A_{j} \le K$
3. $\sum_{j=i+2M}^{i+3M-1}A_{j} \le K$

첫째 줄에 정수 $N$ 과 $K$ 가 주어진다. 둘째 줄에는 배열 $A$ 의 원소 $N$ 개가 순서대로 주어진다.

조건을 만족하는 가장 큰 양의 정수 $M$ 을 출력한다. 그런 $M$ 이 없으면 $0$ 을 출력한다.