페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8597
서브태스크

수열과 쿼리 3s 1024MB

문제

길이 l의 수열 [B_1, B_2, \cdots, B_l]에 대해, 수열의 연속 구간은 [B_i, B_{i+1}, \cdots , B_j]와 같이 수열 위에서 연속적으로 등장하는 수들의 부분 수열로 정의된다.

연속 구간은 비어 있을 수 없다. 즉, 1 ≤ i ≤ j ≤ l을 만족해야 한다.

길이 l의 수열 [B_1, B_2, …. , B_l]에 대해, 수열의 최대 연속 구간 합은 수열의 모든 연속 구간의 원소의 합의 최댓값으로 정의된다.

예를 들어, 수열 [6,-7,3, -1,5, 2]의 최대 연속 구간 합은 9이며, 이는 연속 구간 [3, -1, 5, 2]를 골라서 얻을 수 있다.

수열 B의 최대 연속 구간 합을 수학 기호로 표현하면 max_{1 \le i \le j \le l}(\sum^{j}_{k=i} B_k)이다.

길이 N의 수열 [A_1, A_2, \cdots, A_N]과 Q 개의 쿼리가 주어진다.

i 번째 쿼리는 하나의 정수 X_i로 표현된다. X_i가 주어졌을 때, 수열 [A_1 +X_i, A_2 + X_i, ... ,A_N + X_i]의 최대 연속 구간 합을 계산하라.


입력

첫 번째 줄에 N, Q가 공백을 사이에 두고 주어진다.

두 번째 줄에 A_1, A_2, .. , A_N이 공백을 사이에 두고 주어진다.

세 번째 줄에 X_1, X_2, ... , X_Q가 공백을 사이에 두고 주어진다.

[제약 조건]

  • 주어지는 모든 수는 정수이다.

  • 1<N≤1\ 000\ 000

  • 1<Q≤1\ 000\ 000

  • 1 ≤ i ≤ N인 모든 i에 대해 -10^9 ≤ A_i ≤ 10^9이다.

  • 1 ≤ i ≤ Q인 모든 i에 대해 -10^9 ≤ X_i ≤ 10^9이다.


출력

Q개의 줄을 출력하라. 이 중 i (1 \le i \le Q) 번째 줄에는 수열 [A_1 +X_i, A_2 + X_i, ... ,A_N + X_i]의 최대 연속 구간 합을 출력하라.


부분문제

번호 점수 조건
#15점

N,Q≤300

#25점

N≤300

#328점

N≤10\ 000

#417점

N≤125\ 000

#516점

N≤250\ 000

#615점

N≤500 000

#714점

추가 제약 조건 없음


예제 #1

6 15
6 -7 3 -1 5 2
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
-1
0
1
2
3 
4 
5 
9 
14
20
26
32
38
44
50

예제 #2

10 15
-2 6 3 -8 1 2 0 -3 9 6
-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
2
3
5
7
9
11
13
16
25
34
44
54
64
74
84


출처

2025 KOI 2차 중4/고3
로그인해야 코드를 작성할 수 있어요.