Want to try solving this problem? You can submit your code online if you log in or register.

Following your domination of the fruit sculpture market you've decided to try something new. After hours of thought you've realised the future of art will definitely be BLOCKO, specifically mass produced BLOCKO sculptures.

You've already built the assembly line which consists of a chute at a fixed
position dropping BLOCKO blocks onto a conveyor belt below it. The conveyor belt moves right 1 centimetre each second. A sculpture consists of N blocks of
BLOCKO, the ith of which will drop t_{i} seconds after assembly begins,
have width w_{i} centimetres and height h_{i} centimetres. When a BLOCKO block is
dropped it will fall straight down until its bottom edge hits either the conveyor belt or a previously placed BLOCKO block, where it immediately attaches itself to the sculpture. Note that a falling block will not stop moving if it just
touches corners with another block. Furthermore when each block is dropped,
its right edge will be in line with the right edge of the chute and you may
assume it falls into place instantly.

For instance, consider the sculpture consisting of the following 4 blocks. The first block falls after 1 second, is 2 centimetres tall, and 3 centimetres wide.

The second block falls after 2 seconds, is 1 centimetre tall, and 2 centimetres wide.

The third block falls after 3 seconds, is 1 centimetre tall, and 2 centimetres wide.

The final block falls after 5 seconds, is 3 centimetres tall, and 1 centimetre wide. Thus the final sculpture will be:

Before you can start shipping your art across the world you must first package it. Specifically you need to determine the maximum height any part of the sculpture will be so that you can order boxes of the correct size. In the above example the sculpture's height is 4 centimetres.

N lines will follow, the ith of which will contain the integers t_{i}, w_{i}, and h_{i} describing the ith block. You may assume that
the blocks will be listed in increasing order of time they are placed, that is t_{1} < t_{2} < < t_{N}.

4 1 3 2 2 2 1 3 2 1 5 1 3

4

The sample input corresponds to the scenario described above in the problem statement.

For all subtasks, 1 ≤ N ≤ 100,000, 1 ≤ t_{i}, w_{i} ≤ 1,000,000, and 1 ≤ h_{i} ≤ 1000 for all i.

- For Subtask 1 (20 marks), t
_{i}, w_{i}, N ≤ 1000 and it is guaranteed the the sculpture is at most 1000 centimetres tall. - For Subtask 2 (20 marks), all blocks have the same w
_{i}and the same h_{i}, that is, they all have the same dimensions. Note w_{i}does not have to equal h_{i}, that is, the blocks are not necessarily square. - For Subtask 3 (60 marks), no further constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021, 10:16am AEST