Back From Summer '17 P6: Crowded Cities

Points: 20 (partial)

Time limit: 1.0s

Java 8 1.4s

Python 1.8s

Memory limit: 256M

Python 1G

Problem type

Drake giving good city building advice.

For many 9th grade students enthusiastically starting high school, geography is often one of the first new subjects they encounter. A very important part of geography class is teaching students about the importance of city design. The teacher explains to students how denser cities allow for more efficient transportation and use of resources. Clearly, the key to denser cities is taller buildings that house more people.

Toronto, Canada is facing a housing shortage, so for the last project of the semester, the teacher goes up to the aspiring city designers and asks them to design a building that houses the most people. While all your classmates are off designing weird buildings that will probably crash and burn, your buddy Alex convinces you to use giant lego houses like all the hip kids are supposedly doing.

Each housing block is a rectangular prism with integer length, width, and height. Block $i$ ~i~ has a length of $L_i$ ~L_i~, a width of $W_i$ ~W_i~, a height of $H_i$ ~H_i~ respectively and can house $P_i$ ~P_i~ people.

Unfortunately for medieval designers, overhangs are not popular in Toronto, so they are banned by the city for aesthetic reasons. In addition, city regulations require that windows on a building are aligned by a lattice grid (aka blocks may only be rotated by $90$ ~90~ degrees), and no block may be taller than the block below it. Formally, block $i$ ~i~ can be stacked on top of block $j$ ~j~ if $L_i \le L_j$ ~L_i \le L_j~, $W_i \le W_j$ ~W_i \le W_j~ and $H_i \le H_j$ ~H_i \le H_j~.

You are really interested in qualifying for the geomatics program at the University of Waterloo, so you want to prove your geography skills to the teacher.

Find a design that houses the greatest number of people!

Input Specification

The first line will contain $N$ ~N~ $(N \le 100\,000)$ ~(N \le 100\,000)~, the number of blocks that you have available.

In each of the next $N$ ~N~ lines, there will be 4 integers. On the $i^\text{th}$ ~i^\text{th}~ $(1 \le i \le N)$ ~(1 \le i \le N)~ line there will be $L_i, W_i, H_i$ ~L_i, W_i, H_i~ $(L_i, W_i, H_i \le 5\,000)$ ~(L_i, W_i, H_i \le 5\,000)~, $P_i$ ~P_i~ $(P_i \le 1\,000\,000\,000)$ ~(P_i \le 1\,000\,000\,000)~ that specify the length, width, height in the $i^\text{th}$ ~i^\text{th}~ block, and the number of people you can fit inside.

Output Specification

On the first line, print the greatest number of people that your building can support while adhering to regulations.

On the next line print $K$ ~K~, the number of blocks in your design.

In the next line, print $K$ ~K~ space separated integers indicating the indices of blocks you plan to use. You should first print the blocks from the base upwards.

NOTE: Block indices start at 1.

Constraints

Subtask 1 [10%]

$N \le 9$ ~N \le 9~

Subtask 2 [10%]

$L_i = W_i = H_i$ ~L_i = W_i = H_i~

Subtask 3 [20%]

$N \le 500$ ~N \le 500~

Subtask 4 [20%]

$H_i = 1$ ~H_i = 1~

Subtask 5 [20%]

$L_i, W_i \le 1\,000$ ~L_i, W_i \le 1\,000~

Subtask 6 [20%]

No additional constraints.

Sample Input 1

Sample Output 1

11
2
3 2

Sample Explanation 1

Block 2 is stacked on top of block 3. This is allowed since no dimension of block 2 exceeds that of block 3. When combined, the building can house $5+6=11$ ~5+6=11~ people.

Sample Input 2

Sample Output 2

8
2
1 3

Sample Explanation 2

The optimal solution would be to stack block 3 on top of block 1. Even though stacking block 3 on top of block 2 would allow $4+5=9$ ~4+5=9~ housing units, city regulation does not allow blocks to be stacked on other blocks shorter than them.

Comments

12

Dan13llljws commented on Sept. 14, 2020, 9:17 p.m. ← edited →

Legos don't rotate on all 3 axes :)))

3

discoverMe commented on Jan. 7, 2019, 5:11 p.m.

can you put 2 blocks on top of a block if they both fit

eg. 10x10x10 and 20x5x5 blocks on 100x100x100 block

4

Riolku commented on Feb. 4, 2019, 6:35 p.m.

no