← All solutions

This is a quite tricky problem. We’ll process the machines by order of availability date, and use a carefully built data structure to keep track of what our best options so far are. The data structure consists of a list of straight lines of the form M = c + kD for some constants c and k, indicating that at day D we can have M dollars. We keep this list pruned so that only lines that are the best possible for some day are actually present, and sorted by slope. For a given day D we can find the maximum amount of money for day D in logarithmic time (in C++ STL the most natural way of implementing this gives log-squared time but that’s OK).

When we process a new machine (with availability day D_i), we compute the maximum amount of money available on day D_i. Then, from any day after D_i, a new line is possible by switching to machine i on day D_i. (This new linear function is only valid from day D_i and onwards, but as we’re processing the machines in order by availability day that’s ok.) We then need to add this new line to the list of available lines (and prune away lines that are no longer optimal at any point), which can also be done in logarithmic time.