Szarlotka

면접 대비

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

요약

N개의 정수가 주어질 때, 합이 K에 가장 가까운 비어 있지 않은 연속 부분 배열을 찾아 |합 - K|의 최솟값을 출력합니다.

난이도: 보통10점 중 5점
유형: 누적 합, 이분 탐색
정답자: 아직 제출이 없습니다

문제

바이티나의 바브차 비트카(Babcia Bitka)는 적어도 비트카의 말로는 세상에서 가장 맛있는 사과 파이를 만든다. 비트카는 그녀에게 레시피를 받았고, 가장 중요한 재료인 사과만 빼고 나머지 재료를 모두 모았다.

비트카의 과수원에는 $N$ 그루의 나무가 한 줄로 서 있고, 1번부터 $N$ 번까지 번호가 매겨져 있다. 각 나무에는 사과가 정확히 하나씩 달려 있으며, 사과는 모두 품종이 다르다. $i$ 번 나무의 사과는 단맛이 $A_i$ 이다. 아주 신 사과도 있어서 단맛이 음수일 수 있다.

파이에는 단맛의 합이 $K$ 인 사과가 필요하다. 비트카는 빈틈없이 이어진 나무 구간을 비지 않게 하나 고르고, 그 구간의 사과를 모두 딴다. 딴 사과의 단맛 합을 $S$ 라고 할 때, $|S - K|$ 가 최소가 되도록 구간을 고르려고 한다.

입력

첫 줄에 두 정수 $N$ 과 $K$ 가 주어진다 ( $1 \le N \le 500\,000$ , $-10^{18} \le K \le 10^{18}$ ).

둘째 줄에는 $N$ 개의 정수 $A_1, A_2, \ldots, A_N$ 이 주어진다 ( $-10^{12} \le A_i \le 10^{12}$ ).

출력

$|S - K|$ 의 최솟값을 정수 하나로 출력한다.

예제4

예제 1
입력
```
5 12
4 3 -9 16 9
```
예상 출력
```
2
```
예제 2
입력
```
2 7
-5 -10
```
예상 출력
```
12
```
예제 3
입력
```
8 30
4 12 12 10 -5 15 6 -5
```
예상 출력
```
1
```
예제 4
입력
```
6 10
1 4 20 -21 8 4
```
예상 출력
```
1
```