Hello,

I am working on USACO Bronze December 2015 Problem 2: Speeding Ticket. Link: Speeding Ticket.

I’ve read through the USACO Guide official solution for it. Link: solution

I feel like it can be done faster with prefix sums. The idea being that instead of breaking everything up into segments of length 1, you can iterate with 2 pointers. You increment the road pointer when Bessie has traveled more than the prefix sum of the current road index. You increment Bessie’s index when there is more road left to traverse.

I coded it up and it passed 6/10 test cases. I cannot seem to figure out why it does not work. What is the counter example?

Here is my current code:

```
#include <cstdio>
using namespace std;
inline int max(int a, int b) {
return (a >= b ? a : b);
}
inline int min(int a, int b) {
return (a <= b ? a : b);
}
int main() {
FILE* input_file = fopen("speeding.in", "r");
FILE* output_file = fopen("speeding.out", "w");
int n, m;
fscanf(input_file, "%d %d", &n, &m);
int* road_prefix_sum = new int[n];
int* road_speed = new int[n];
int* travel_length = new int[m];
int* travel_speed = new int[m];
int speed, dist, total=0;
for (int i = 0; i < n; i++) {
fscanf(input_file, "%d %d", &dist, &speed);
total += dist;
road_prefix_sum[i] = total;
road_speed[i] = speed;
}
for (int i = 0; i < m; i++) {
fscanf(input_file, "%d %d", &dist, &speed);
travel_length[i] = dist;
travel_speed[i] = min(100, speed);
}
int road_index = 0;
int travel_index = 0;
int travel_total = 0;
int max_speeding = 0;
while (travel_total < 100 || road_index < n) {
if (travel_total < road_prefix_sum[road_index]) {
max_speeding = max(max_speeding, travel_speed[travel_index] - road_speed[road_index]);
travel_total += travel_length[travel_index];
travel_index++;
} else {
if (travel_total != road_prefix_sum[road_index]) {
max_speeding = max(max_speeding, travel_speed[travel_index] - road_speed[road_index]);
}
road_index++;
}
}
fprintf(output_file, "%d", max_speeding);
fclose(input_file);
fclose(output_file);
return 0;
}
```

Appreciate the help. Thanks in advance!