2회 문제풀이 09 / ABC 135 C - City Savers
ABC 135 C - City Savers
【문제 개요】
N + 1개의 마을이 있습니다. i번째의 마을은 Ai체의 몬스터에게 공격당하고 있습니다.
N명의 용사가 있으며 i번째의 용사는 i번째 또는 i+1번째의 마을을 공격하는 몬스터를 합계 Bi체까지 쓰러트릴 수 있습니다.
N명의 용사가 잘 협력하여 최대 몇체의 몬스터를 쓰러트릴 수 있을까요?
힌트 : 이진 탐색 알고리즘
【전제】
- 입력은 전부 정수이다.
- 1 ≦ N ≦ 10^5
- 1 ≦ Ai ≦ 10^9
- 1 ≦ Bi ≦ 10^9
【입력 형태】
1
2
3
N
A1 A2 ... AN AN+1
B1 B2 ... BN
【출력 형태】
쓰러트린 몬스터의 합계의 최대치를 출력하시오.
【예시】
입력 예 1
1
2
3
2
3 5 2
4 5
출력 예 1
1
9
이하와 같이 몬스터를 쓰러트리면 합계 9체의 몬스터를 쓰러트리는것이 가능하며, 이것이 최대이다.
- 1번째의 용사가 1번째의 마을을 습격한 몬스터를 2체, 2번째의 마을을 습격한 몬스터를 2체 쓰러트린다.
- 2번째의 용사가 2번째의 마을을 습격한 몬스터를 3체, 3번째의 마을을 습격한 몬스터를 2체 쓰러트린다.
입력 예 2
1
2
3
3
5 6 3 8
5 100 8
출력 예 2
1
22
입력 예 3
1
2
3
2
100 1 1
1 100
출력 예 3
1
3
ABC 135 C - City Savers
【문제 개요】
N + 1개의 마을이 있습니다. i번째의 마을은 Ai체의 몬스터에게 공격당하고 있습니다.
N명의 용사가 있으며 i번째의 용사는 i번째 또는 i+1번째의 마을을 공격하는 몬스터를 합계 Bi체까지 쓰러트릴 수 있습니다.
N명의 용사가 잘 협력하여 최대 몇체의 몬스터를 쓰러트릴 수 있을까요?
힌트 : 이진 탐색 알고리즘
【전제】
- 입력은 전부 정수이다.
- 1 ≦ N ≦ 10^5
- 1 ≦ Ai ≦ 10^9
- 1 ≦ Bi ≦ 10^9
【입력 형태】
1
2
3
N
A1 A2 ... AN AN+1
B1 B2 ... BN
【출력 형태】
쓰러트린 몬스터의 합계의 최대치를 출력하시오.
【예시】
입력 예 1
1
2
3
2
3 5 2
4 5
출력 예 1
1
9
이하와 같이 몬스터를 쓰러트리면 합계 9체의 몬스터를 쓰러트리는것이 가능하며, 이것이 최대이다.
- 1번째의 용사가 1번째의 마을을 습격한 몬스터를 2체, 2번째의 마을을 습격한 몬스터를 2체 쓰러트린다.
- 2번째의 용사가 2번째의 마을을 습격한 몬스터를 3체, 3번째의 마을을 습격한 몬스터를 2체 쓰러트린다.
입력 예 2
1
2
3
3
5 6 3 8
5 100 8
출력 예 2
1
22
입력 예 3
1
2
3
2
100 1 1
1 100
출력 예 3
1
3
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。