레이팅 미적용언제나 말썽꾸러기인 소 베시가 농부 존의 트랙터를 훔쳐 도로를 질주했다!
도로의 길이는 정확히 100마일이며, 베시는 도로 전체를 달린 끝에 결국 경찰관에게 붙잡혔다. 경찰관은 베시에게 제한 속도 초과, 면허 만료, 그리고 소가 자동차를 운전한 죄로 딱지를 발부했다. 베시는 뒤의 두 딱지는 아마 타당하다고 인정하지만, 속도위반 딱지가 정당하게 발부된 것인지는 의문을 품고 있으며, 여정의 일부에서 실제로 제한 속도보다 빠르게 달렸는지 직접 확인해 보고 싶어 한다.
도로는 \(N\)개의 구간으로 나뉘어 있으며, 각 구간은 마일 단위의 양의 정수 길이와 \(1 \ldots 100\) 범위의 정수 제한 속도(마일/시)로 표현된다. 도로의 길이가 100마일이므로 \(N\)개 구간의 길이의 합은 100이다. 예를 들어 도로는 길이 45마일, 제한 속도 70인 구간으로 시작해서, 길이 55마일, 제한 속도 60인 구간으로 끝날 수 있다.
베시의 여정 역시 \(M\)개의 구간으로 표현된다. 각 구간에서 베시는 특정 양의 정수 마일만큼을 특정 정수 속도로 달린다. 예를 들어 처음에 50마일을 속도 65로 달리고, 그다음 50마일을 속도 55로 달릴 수 있다. \(M\)개 구간의 길이의 합은 총 100마일이다. 농부 존의 트랙터는 최고 시속 100마일까지 달릴 수 있다.
위 정보가 주어질 때, 베시가 여정의 어느 부분에서든 제한 속도를 초과한 최대량을 구하시오.
Problem credits: Austin Bannister and Brian Dean
Problem credits: Austin Bannister and Brian Dean
입력의 첫째 줄에 \(N\)과 \(M\)이 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에는 각각 도로 구간을 나타내는 두 정수인 길이와 제한 속도가 주어진다.
다음 \(M\)개의 줄에는 각각 베시의 여정의 한 구간을 나타내는 두 정수인 길이와 베시가 달린 속도가 주어진다.
베시가 여정의 어느 부분에서든 제한 속도를 초과한 최대량을 한 줄에 출력한다. 베시가 제한 속도를 한 번도 초과하지 않았다면 0을 출력한다.
speeding.in · 출력을 쓸 파일 speeding.out3 3
40 75
50 35
10 45
40 76
20 30
40 405In this example, the road contains three segments (40 miles at 75
miles per hour, followed by 50 miles at 35 miles per hour, then 10
miles at 45 miles per hour). Bessie drives for three segments (40
miles at 76 miles per hour, 20 miles at 30 miles per hour, and 40
miles at 40 miles per hour). During her first segment, she is
slightly over the speed limit, but her last segment is the worst
infraction, during part of which she is 5 miles per hour over the
speed limit. The correct answer is therefore 5.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Bronze