Editorial for IOI '04 P4 - Phidias - Olympiads Online Judge

Editorial for IOI '04 P4 - Phidias

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Use Dynamic Programming:

Let $a(x, y)$ $a (x, y)$ be the wasted area for a rectangle $(x, y)$ $(x, y)$ , $1 \le x \le W$ $1 \leq x \leq W$ , $1 \le y \le H$ $1 \leq y \leq H$ . Initially, put $a(x, y) = xy$ $a (x, y) = x y$ , for all $(x, y)$ $(x, y)$ except for the ones corresponding to needed plates, e.g. $x = w_i$ $x = w_{i}$ and $y = h_i$ $y = h_{i}$ , $1 \le i \le N$ $1 \leq i \leq N$ , for which we put $a(x, y) = 0$ $a (x, y) = 0$ . For a plate $(x, y)$ $(x, y)$ consider all vertical cuts $c = 1, 2, \dots, x-1$ $c = 1, 2, \dots, x - 1$ and all horizontal cuts $c = 1, 2, \dots, y-1$ $c = 1, 2, \dots, y - 1$ and chose the cut producing the minimum wasted area $a(x, y) = a(c, y) + (x-c, y)$ $a (x, y) = a (c, y) + (x - c, y)$ or $a(x, c) + a(x, y-c)$ $a (x, c) + a (x, y - c)$ for some $c$ $c$ .

Comments

There are no comments at the moment.