USACO 2015 December Contest Bronze Division - Speeding Ticket

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be solved using brute force because the sum of all lengths is at most 100.

As an alternative, we can rely on doing some sort of sweeping through the queries to assess whenever the speed limit was broken but this is beyond what we need for this problem.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ifstream cin("speeding.in");
    ofstream cout("speeding.out");

    int n, m, speedLimit[101];
    cin >> n >> m;

    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        int len, val;
        cin >> len >> val;
        for(int j = sum+1; j <= sum + len; j++)
            speedLimit[j] = val;
        sum += len;
    }

    int pos = 0, maxi = 0;
    for(int i = 1; i <= m; i++)
    {
        int len, val;
        cin >> len >> val;
        for(int j = pos + 1; j <= pos + len; j++)
            maxi = max(maxi, val - speedLimit[j]);
        pos += len;
    }

    cout << maxi;
    return 0;
}

with open("speeding.in", "r") as fin:
    n, m = map(int, fin.readline().split())
    speedLimit = [0] * 101
    sum_ = 0
    for i in range(n):
        length, val = map(int, fin.readline().split())
        for j in range(sum_ + 1, sum_ + length + 1):
            speedLimit[j] = val
        sum_ += length
    pos = 0
    maxi = 0
    for i in range(m):
        length, val = map(int, fin.readline().split())
        for j in range(pos + 1, pos + length + 1):
            maxi = max(maxi, val - speedLimit[j])
        pos += length

with open("speeding.out", "w") as fout:
    fout.write(str(maxi))