Programozás‎ > ‎Feladatok‎ > ‎

Kiwi szörp

Taro finom kiwi szörpöt készített, majd N üvegbe öntötte szét (az üvegek 0-tól (N-1)-ig számozottak. Minden üvegbe C liter szörp fér, és kezdetben bottles[i] litert töltött az i. üvegbe. Taro el akarja adni a szörpöt, de előtte tetszőlegesen sokszor végrehajthatja az alábbi műveletet: két különböző üveget választva (A és B) A-ból B-be addig töltheti a szörpöt, amíg
  • vagy A kiürül,
  • vagy B megtelik. 
(Amelyik előbb bekövetkezik, azt kell végrehajtani.)

Ha egy üveg x lliter kiwi szörpöt tartalmaz (0 <= x <= C), akkor Taro prices[x] dollárért tudja eladni ezt az üveget. 

Feladat

Írjunk programot, ami kiszámolja, hogy Taro legfeljebb hány dollárt tud keresni.

Bemenet

A bemenet első sorában C található (1 <= C < 50).
Ezután az üvegekbe kezdetben betöltött szörp mennyisége jön (bottles[]) egy sorban, szóközökkel elválasztva. Legfeljebb 15 üveg van.
Végül a harmadik sorban a prizes[] tömb elemei vannak megadva, pontosan C+1 egész, 0-tól C-ig indexelve értendő. Minden ár 0 és 1000000 közé esik, a határokat is megengedve.

Kimenet

A maximálisan kereshető pénzérték.

Példa

Bemenet  Kimenet
10
5 8
0 0 0 0 0 0 0 0 0 0 10		10
10
5 8
0 0 0 0 0 10 10 10 10 10 10		20
10
4 5 3 7
14 76 12 35 6 94 26 3 93 90 420		625
1
0
1000000 1000000		1000000
49
2 47 24 14 0 32 9 12 31 46 39 12 16 22 29
428668 995687 128567 37241 496916 238624 304781 997819 85856 417008 398570 951499 750349 333625 927594 188616 942498 259414 654344 354809 25303 226854 98578 207140 305527 358343 393213 256248 282644 103327 667191 103402 609183 619323 189127 518006 778846 400460 128334 795097 605203 669142 121825 934404 837430 554265 610818 546228 80784 949440		 12873962


Címkék

Algoritmusok: dinamikus programozás