레이팅 미적용설명
농부 존은 N개의 커다란 건초 더미(1 <= N <= 4000)를 배송받아 길을 따라 여러 위치에 놓아 두었다. 소 베시는 길을 따라 풀을 뜯고 있었는데, 이제 건초 더미들 사이에 갇혀 버렸을지도 모른다!
각 건초 더미 j는 크기 S_j와 일차원 길 위의 서로 다른 위치 P_j를 가진다. 베시는 건초 더미가 없는 어떤 위치에서 출발하며, 건초 더미의 위치까지는 길을 따라 자유롭게 이동할 수 있지만 더미를 통과할 수는 없다. 예외적으로, 같은 방향으로 D만큼의 거리를 달리면 충분한 속도가 붙어서 크기가 D보다 엄밀히 작은 건초 더미를 뚫고 지나가 영구히 없앨 수 있다. 이렇게 하고 나면 더 넓은 공간이 생겨 다른 더미들도 뚫을 수 있게 될지 모른다.
베시는 결국 가장 왼쪽 또는 가장 오른쪽 더미를 뚫을 수 있으면 탈출할 수 있다. 베시가 탈출할 수 없는 실수 값 출발 위치들로 이루어진 길 구간의 총 넓이를 계산하시오.
제약
입력 형식
첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각각 건초 더미를 나타내는 두 정수인 크기와 위치가 주어지며, 각각 1...10^9 범위이다.
출력 형식
베시가 탈출할 수 없는 길 구간의 넓이를 하나의 정수로 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
trapped.in · 출력을 쓸 파일 trapped.out예제 1
입력
5
8 1
1 4
8 8
7 15
4 20출력
14문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > US Open > Bronze
태그