RAD's blog

By RAD, 14 years ago, translation, In English

Let's divide all trucks into the classes by l + r + c. It can be seen, that all the trucks that can be included in the answer are in the same class.

Let's solve the problem separately for each class. Consider all trucks from same class in the order they appear, and keep the following value: z[k] = the maximum sum that you can get, if the last taken truck has ri = k. Consider the truck number i - there are 2 options to update z:

It can update z[ri] with z[ri + ci] + vi, i. e. continue the motorcade, which has last truck with r = ri + ci. (For neighboring trucks should be true the following: rprev  =  ri  +  ci)

If li = 0, it can update z[ri] with vi, i. e. became the first truck in the new motorcade. (For the first truck should be true the following: li = 0)

The answer will be in z[0].

To restore the trucks included in the answer, we can keep with the maximal sum in z the index of last truck that updated this sum. Also we store the ancestor p for each truck that updated something in z. This ancestor is calculated when we consider i-th truck and doesn't change further: p[i] = -1 if truck i became beginning of the motorcade, otherwise p[i] = last truck that updated z[ri  +  ci].

We start restore of the answer from last truck updated z[0]. After that we restore everything using only p.

  • Vote: I like it
  • +6
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
During the competition I misunderstood the problem statement. I thought that each truck wants AT LEAST l/r people to go before/after this truck. The reason was the first paragraph where it was said that some people do not want to be first and some do not want do be the last ones. It took me more than 20 minutes to discover my mistake (because my program gave different answer on the first example test). I know that I should have checked sample tests carefuly before coding, but in my opinion adding a word "exactly" in the problem statement would help.

PS The task with "at least" is also solvable with the same limits on input data.
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I made the same mistake. problem statement was ambiguous.