산책로
다이아몬드 V의견: 0
KOI 산에는 \(1\)번부터 \(N\)번까지 번호가 부여된 \(N\)개의 쉼터가 있고, 그 쉼터들을 잇는 \(N-1\)개의 양방향 산책로가 있다.
\(i\) (\(1 \le i \le N\))번 쉼터에 사람이 얼마나 많은지를 나타내는 밀집도는 양의 정수 \(A_i\)로 나타낼 수 있다.
\(j\) (\(1 \le j \le N-1\))번째 산책로는 \(j\)번 쉼터와 \(C_j\)번 쉼터를 이으며 (\(j+1 \le C_j \le N\)), 그 길이는 \(L_j\)이다. 즉, 쉼터들은 산책로를 통해 연결된 트리 구조를 이룬다.
고독한 산책가 교준이는 서로 다른 두 쉼터를 골라, 두 쉼터 사이의 유일한 단순 경로를 따라 산책하려고 한다. 어떤 경로를 선택했을 때,
- 경로에 포함된 산책로의 길이의 합을 \(S\),
- 경로에 포함된 쉼터의 밀집도의 최댓값을 \(M\)
이라고 하자. 교준이는 산책을 길게, 그러나 사람이 적은 곳에서 고독하게 즐기고 싶기 때문에, 이 경로의 만족도는 \(S - M\)으로 정의된다.
교준이가 산책할 경로의 만족도를 최대화하기 위해서는 어떤 두 쉼터를 골라야 하는지 계산하는 프로그램을 작성하라.
- 주어지는 모든 수는 정수이다.
- \(2 \le N \le 300\,000\)
- 모든 \(i\) (\(1 \le i \le N\))에 대하여 \(1 \le A_i \le 10^{18}\)
- 모든 \(j\) (\(1 \le j \le N-1\))에 대하여 \(j+1 \le C_j \le N\)이고 \(1 \le L_j \le 10^{12}\)
첫 줄에 정수 \(N\)이 주어진다.
그다음 줄에 \(N\)개의 정수 \(A_1, A_2, \cdots, A_N\)이 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 \(N-1\)개의 정수 \(C_1, C_2, \cdots, C_{N-1}\)이 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 \(N-1\)개의 정수 \(L_1, L_2, \cdots, L_{N-1}\)이 공백으로 구분되어 차례대로 주어진다.
첫 줄에 경로의 만족도가 최대가 되는 서로 다른 두 쉼터의 번호를 공백으로 구분하여 출력한다.
가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 8점 | \(N \le 300\) |
2 | 12점 | \(N \le 7\,500\) |
3 | 11점 | \(A_1 = A_2 = \cdots = A_N\) |
4 | 15점 | 모든 \(j\) (\(1 \le j \le N-1\))에 대하여 \(C_j = j + 1\)이다. |
5 | 17점 | \(C_1 = C_2 = \cdots = C_{N-1} = N\) |
6 | 36점 | 집합 \(\{A_1, A_2, \cdots, A_N\}\)에 등장하는 서로 다른 정수의 개수는 \(20\) 이하이다. |
7 | 51점 | 추가 제약 조건 없음. |
2
1 2
2
1
1 2
\(1\)번 쉼터와 \(2\)번 쉼터 사이의 경로의 만족도는 \(-1\)로 최대이다.
4
6 10 20 1
2 4 4
3 21 15
1 3
가능한 모든 경로의 만족도는 다음과 같다.
- 경로 \(1 - 2\)의 만족도는 \(3 - \max\{6, 10\} = 3 - 10 = -7\).
- 경로 \(1 - 2 - 4 - 3\)의 만족도는 \((3 + 21 + 15) - \max\{6, 10, 20, 1\} = 39 - 20 = 19\).
- 경로 \(1 - 2 - 4\)의 만족도는 \((3 + 21) - \max\{6, 10, 1\} = 24 - 10 = 14\).
- 경로 \(2 - 4 - 3\)의 만족도는 \((21 + 15) - \max\{10, 20, 1\} = 36 - 20 = 16\).
- 경로 \(2 - 4\)의 만족도는 \(21 - \max\{10, 1\} = 21 - 10 = 11\).
- 경로 \(3 - 4\)의 만족도는 \(15 - \max\{20, 1\} = 15 - 20 = -5\).
따라서 만족도가 \(19\)로 최대인 경로 \(1 - 2 - 4 - 3\)의 양 끝점인 \(1\)번과 \(3\)번 쉼터를 출력한다.
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2026 > 1차 대회 > 중등부 3번 / 고등부 2번
평가 및 의견
산책로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
산책로