문제
Bitaro, 용감한 영웅은 몬스터들을 물리치기 위해 모험을 떠납니다.
몬스터는
Bitaro는 다음 전략을 사용하여 모든 몬스터를 물리치고자 합니다:
시작은 특정 몬스터
j (1 ≤ j ≤ N )부터 시작하여j, j+1, \cdots, N 번 몬스터 순서대로 물리칩니다.만약 j ≥ 2라면, 돌아가서
1, 2, \cdots, j−1 번 몬스터 순서대로 물리칩니다.
주어진 몬스터들의 정보(
입력
첫 번째 줄에 정수 N이 주어집니다.
두 번째 줄에는 N개의 정수 A₁, A₂, …, A_N이 공백으로 구분되어 주어집니다.
세 번째 줄에는 N개의 정수 B₁, B₂, …, B_N이 공백으로 구분되어 주어집니다.
[제한]
2 ≤ N ≤ 500\ 000 0 ≤ A_i ≤ 10^9 (1 ≤ i ≤ N )0 ≤ B_j ≤ 10^9 (1 ≤ j ≤ N )주어지는 입력은 모두 정수
출력
단일 정수
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | |
| #2 | 21점 | |
| #3 | 19점 | 최소 초기 힘 |
| #4 | 22점 | 모든 |
| #5 | 28점 | 추가 제약 조건 없음 |
예제 #1
5
1 3 2 8 6
4 3 1 1 2
1
x = 1로 시작할 경우, 몬스터들을 1번부터 순서대로 물리치면 다음과 같이 진행됩니다:
몬스터 1: 현재 힘 1 ≥ 1, 승리 후 힘 1+4 = 5
몬스터 2: 5 ≥ 3, 힘 5+3 = 8
몬스터 3: 8 ≥ 2, 힘 8+1 = 9
몬스터 4: 9 ≥ 8, 힘 9+1 = 10
몬스터 5: 10 ≥ 6, 힘 10+2 = 12
따라서 x = 1이면 모든 몬스터를 물리칠 수 있으므로 최소 초기 힘은 1입니다.
예제 #2
5
1 6 3 3 2
1 2 1 0 1
3
x = 3일 때, 전략에 따라 3번 몬스터부터 시작하면:
몬스터 3: 3 ≥ 3, 힘 3+1 = 4
몬스터 4: 4 ≥ 3, 힘 4+0 = 4
몬스터 5: 4 ≥ 2, 힘 4+1 = 5
이후 1번 몬스터: 5 ≥ 1, 힘 5+1 = 6
2번 몬스터: 6 ≥ 6, 힘 6+2 = 8
따라서 x = 3이면 모든 몬스터를 물리칠 수 있으므로 답은 3.
예제 #3
10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1
9
최적의 전략을 사용하면, x = 9로 시작할 때 특정 회전(예: 5번 몬스터부터 시작)으로 모든 몬스터를 물리칠 수 있습니다.
예제 #4
7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580
0
x = 0인 경우, 3번 몬스터부터 시작하면 모든 몬스터를 물리칠 수 있습니다. (예: 몬스터 3의 요구 힘은 0이므로 x = 0으로도 시작 가능)
로그인해야 코드를 작성할 수 있어요.