Notice that if we know Bessie's maximum possible speed at each turn, we can use some simple math to derive her maximum possible speed over the whole course. Thus we can reduce the problem to finding Bessie's maximum possible speed at each turn.
First, sort the turns in order by their distance from the start.
Now, Bessie's maximum speed at turn i - "M_i" - is dictated by three constraints:
One way to calcualte the solution starts with a "fake turn" at the starting line for which M_i = 1 meter/second, and then calculating M_i for each successive turn. To account for the possibility of Bessie's fastest speed coming at the end of the course, we put another "fake turn" with infinite speed limit at L meters from the start.
For each turn, a straightforward but slightly suboptimal formulation of our constraints above gives:
M_i = min(M_{i-1} + (T_i - T_{i-1}), S_j + (T_j - T_i) for all j > i, S_i)
Since we would have examine up to N constraints for each of the N turns, this solution would be too slow for larger values of N, but would succeed for a majority of the test cases.
Note that the first constraint deals with how quickly Bessie can speed up from the last turn, while the second and third constraints deal with keeping her speed low so she can slow down to meet the speed limit for this and all remaining turns. For this reason, it is quicker to sweep backwards over the turns and precompute the minimum value of the second and third constraints - call this speed "m_i" - for each value of i.
If Bessie cannot be going faster than m_i in order to meet the speed limits for turns i and above, then she cannot be going faster than min(m_i + (T_i - T_{i-1}), S_{i-1}) to meet the speed limits for turn i-1 and above. We therefore sweep backwards across the speeds and precompute the recurrence:
m_i = min(m_i + (T_i - T_{i-1}), S_{i-1})
and then sweep forward and compute the recurrence
M_i = min(M_{i-1} + (T_i - T_{i-1}), m_i)
Because we only sweep through the turns twice, this algorithm runs
in linear time, running quickly even for N=100,000.
The specifics of the starting conditions for the recurrences, as well as the math to find the maximum speed between two turns, is in the code below. The code uses the "speedup" array to hold M_i and the "slowdown" array to hold m_i. Sample solution:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define MAX 100005
#define INF 2000000000
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
using namespace std;
int L, N;
struct turn {
int T, S;
};
turn turns[MAX+2];
int slowdown[MAX+2], speedup[MAX+2];
int cmp(const void *a, const void *b) {
turn p = *(turn *)a, q = *(turn *)b;
if (p.T < q.T) return -1;
else if (p.T > q.T) return 1;
else return 0;
}
inline int maxbetween(int s1, int s2, int dist) {
return max(s1, s2) + int((dist - abs(s1 - s2)) / 2);
}
int main() {
FILE *in = fopen("bobsled.in", "r");
FILE *out = fopen("bobsled.out", "w");
// Read data and add in "fake turns"
fscanf (in, "%d%d", &L, &N);
turns[0].T = 0;
turns[0].S = 1;
for (int i = 1; i <= N; i++) {
fscanf(in, "%d%d", &turns[i].T, &turns[i].S);
}
turns[N+1].T = L;
turns[N+1].S = INF;
N += 2;
qsort (turns, N, sizeof(turns[0]), cmp);
// Compute slowdown 'm_i'
slowdown[N-1] = turns[N-1].S;
for (int i = N-2; i >= 0; i--) {
slowdown[i] = min(slowdown[i+1] + (turns[i+1].T - turns[i].T),
turns[i].S);
}
// Compute speedup, aka 'M_i', and find maximum speeds between turns
int maxspeed = 1;
speedup[0] = turns[0].S;
for (int i = 1; i < N; i++) {
speedup[i] = min(speedup[i-1] + (turns[i].T - turns[i-1].T),
slowdown[i]);
maxspeed = max(maxspeed,
maxbetween(speedup[i-1],
speedup[i],
turns[i].T - turns[i-1].T));
}
fprintf(out, "%d\n", maxspeed);
return 0;
}