시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 288 39 34 20.238%

문제

You are given an array $A_{0}$, $A_{1}$, $A_{2}$, $...$ , $A_{N-1}$ of $N$ positive integers. Also, you are given an positive integer $K$. Your task is to find the largest positive integer $M$ such that the following condition is satisfied:

  • There exists an integer $0 \le i \le N-3M$ such that
    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$

입력

The first line contains two integers, $N$ and $K$. The second line contains $N$ integers, the array $A$ given in order.

출력

Output a single positive integer denoting the largest possible $M$. If there is no such $M$, output $0$.

제한

  • $1 \le N \le 5 \times 10^{5}$
  • $1 \le K \le 10^{9}$
  • $1 \le A_{i} \le 10^{9}$

서브태스크 1 (10점)

This subtask has an additional constraint: 

  • $N \le 100$

서브태스크 2 (20점)

This subtask has an additional constraint: 

  • $N \le 10000$

서브태스크 3 (70점)

This subtask has no additional constraints.

예제 입력 1

10 10
3 7 4 3 1 3 5 2 5 1

예제 출력 1

2

출처

University > KAIST > 2021 KAIST RUN Spring Contest D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.