Életszínvonal
Egy város blokkokra van osztva, a blokkok egy téglalapba vannak elrendezve és két koordinátával írhatók le (R,C).
Minden blokknak megadtuk egy mérőszámát, a blokkbeli "életszínvonal" mutatóját. Ezek a számok mind különböznek, értékük 1 és R*C közötti. (A nagyobb a rosszabb.)
A városfejlesztéssel foglalkozó bizottság HxW méretű blokk-téglalapok életszínvonalát definiálja a következő módon: H és W páratlan egészek, és nem haladják meg R illetve C értékét. A téglalap életszínvonal mutatója a benne található blokkok életszínvonalának mediánja.
Feladat
Adjuk meg legjobb életszínvonalú H x W méretű téglalap életszínvonalát!
Bemenet
Adott R, C, H és W értéke, továbbá a blokkok életszínvonal mutatója.
A legnagyobb bemenetre R és C 3000. A programnak 10 másodpercen belül le kell futnia.
Kimenet
Az adott (H,W) méretű téglalapokra kapható legjobb (legkisebb) érték.
Példák
R=5, C=5, H=3, W=3,
Q= 5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
opt = 9
R=2, C=6, H=1, W=5,
Q= 6 1 2 11 7 5
9 3 4 10 12 8
opt = 5
Tesztadatok
