수열과 쿼리 46
다이아몬드 II의견: 0
길이 \(l\)의 수열 \([B_1 , B_2 , \dots , B_l ]\)에 대해, 수열의 연속 구간은 \([B_i , B_{i+1} ,\dots , B_j ]\)와 같이 수열 위에서 연속적으로 등장하는 수들의 부분 수열로 정의된다. 연속 구간은 비어 있을 수 없다. 즉, \(1 ≤ i ≤ j ≤ l\)을 만족해야 한다.
길이 \(l\)의 수열 \([B_1 , B_2 , \dots , B_l ]\)에 대해, 수열의 최대 연속 구간 합은 수열의 모든 연속 구간의 원소의 합의 최댓값으로 정의된다. 예를 들어, 수열 \([6, −7, 3, −1, 5, 2]\)의 최대 연속 구간 합은 \(9\)이며, 이는 연속 구간 \([3, −1, 5, 2]\)를 골라서 얻을 수 있다. 수열 \(B\)의 최대 연속 구간 합을 수학 기호로 표현하면 \(\max_{1 \le i \le j \le l}{\left( \sum_{k=i}^j{B_k} \right)}\)이다.
길이 \(N\)의 수열 \([A_1 , A_2 , \dots , A_N ]\)과 \(Q\)개의 쿼리가 주어진다. \(i\)번째 쿼리는 하나의 정수 \(X_i\)로 표현된다. \(X_i\)가 주어졌을 때, 수열 \([A_1 + X_i , A_2 + X_i , \dots , A_N + X_i ]\)의 최대 연속 구간 합을 계산하라.
- 주어지는 모든 수는 정수이다.
- \(1 \le N \le 1\,000\,000\)
- \(1 \le Q \le 1\,000\,000\)
- \(1 \le i \le N\)인 모든 \(i\)에 대해 \(-10 \le A_i \le 10\)이다.
- \(1 \le i \le Q\)인 모든 \(i\)에 대해 \(-10 \le X_i \le 10\)이다.
첫 번째 줄에 \(N\), \(Q\)가 공백을 사이에 두고 주어진다.
두 번째 줄에 \(A_1 , A_2 , \dots , A_N\)이 공백을 사이에 두고 주어진다.
세 번째 줄에 \(X_1 , X_2 , \dots , X_Q\)가 공백을 사이에 두고 주어진다.
\(Q\)개의 줄을 출력하라. 이 중 \(i\) (\(1 ≤ i ≤ Q\))번째 줄에는 수열 \([A_1 + X_i , A_2 + X_i , \dots , A_N + X_i ]\)의 최대 연속 구간 합을 출력하라.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 5점 | \(N, Q \le 300\) |
2 | 5점 | \(N \le 300\) |
3 | 28점 | \(N \le 10\,000\) |
4 | 17점 | \(N \le 125\,000\) |
5 | 16점 | \(N \le 250\,000\) |
6 | 15점 | \(N \le 500\,000\) |
7 | 14점 | 추가 제약 조건 없음. |
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
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
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 중등부 4번 / 고등부 3번
평가 및 의견
수열과 쿼리 46
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
수열과 쿼리 46