USACO 2015 Feb Bronze

Problem 2. Speeding Ticket

Always the troublemaker, Bessie the cow has stolen Farmer John’s tractor and taken off down the road! The road is exactly 100 miles long, and Bessie drives the entire length of the road before ultimately being pulled over by a police officer, who gives Bessie a ticket for exceeding the speed limit, for having an expired license, and for operating a motor vehicle while being a cow. While Bessie concedes that the last two tickets are probably valid, she questions whether the police officer was correct in issuing the speeding ticket, and she wants to determine for herself if she has indeed driven faster than the speed limit for part of her journey.

The road is divided into N segments, each described by a positive integer length in miles, as well as an integer speed limit in the range 1…100 miles per hour. As the road is 100 miles long, the lengths of all N segments add up to 100. For example, the road might start with a segment of length 45 miles, with speed limit 70, and then it might end with a segment of length 55 miles, with speed limit 60.

Bessie’s journey can also be described by a series of segments, M of them. During each segment, she travels for a certain positive integer number of miles, at a certain integer speed. For example, she might begin by traveling 50 miles at a speed of 65, then another 50 miles at a speed of 55. The lengths of all M segments add to 100 total miles. Farmer John’s tractor can drive 100 miles per hour at its fastest.

Given the information above, please determine the maximum amount over the speed limit that Bessie travels during any part of her journey.

INPUT FORMAT (file speeding.in):
The first line of the input contains N and M, separated by a space.
The next N lines each contain two integers describing a road segment, giving its length and speed limit.

The next M lines each contain two integers describing a segment in Bessie’s journey, giving the length and also the speed at which Bessie was driving.

OUTPUT FORMAT (file speeding.out):
Please output a single line containing the maximum amount over the speed limit Bessie drove during any part of her journey. If she never exceeds the speed limit, please output 0.
SAMPLE INPUT:

SAMPLE OUTPUT:

In 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.

Problem credits: Austin Bannister and Brian Dean

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fin, fout = open('speeding.in'), open('speeding.out', 'w')

N, M = tuple(map(int, fin.readline().split()))

road = []
for _ in range(N):
    f = list(map(int, fin.readline().strip().split()))
    for _ in range(f[0]):
        road.append(f[1])

bessie = []
for i in range(M):
    f = list(map(int, fin.readline().strip().split()))
    for _ in range(f[0]):
        bessie.append(f[1])

ans = 0
for i in range(100):
    r = road[i]
    b = bessie[i]
    ans = max(b - r, ans)

fout.write(str(ans))