A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Meseországban rövid kirándulást teszünk, ahol az úthálózat nagyon egyszerű: az érdekes helyszín mind egyetlen kör alakú út mentén helyezkedik el sorban. Kaptunk egy varázstérképet, amiről rögtön tudjuk, hogy melyik helyszín mennyire érdekes. A kirándulást bármelyik helyszínen elkezdhetjük, és bárhol befejezhetjük, viszont csak percünk van. A térképről tudjuk bármely két szomszédos helyszínről, hogy mennyi ideig tart az út (az -edik és az -edik helyszín között percig (pozitív egész), az -edik és az első helyszín között pedig az út percig tart). Írjunk programot, amely a térkép alapján megtervez egy maximális érdekességű kirándulást (az érdekesség a meglátogatott helyszínek érdekességének összege; minden helyszín legfeljebb egyszer számít), és amely maximum percig tart. (A helyszínek megtekintésének idejét nem vesszük figyelembe.) A standard bemenet első sora tartalmazza a helyszínek számát és a percek számát (egész számok). A második sor egész számot tartalmaz, az -edik szám értéke az -edik helyszín érdekessége. A harmadik sor számot tartalmaz, az -edik szám értéke. A standard kimenet első és egyetlen sorába írjuk ki a legérdekesebb út érdekességét. Pontozás: Az első két tesztesetben . További két tesztesetben . Korlátok: , .
Magyarázat: a második helyszínről indulva a harmadik helyszínen át a negyedik helyszínen befejezve az érdekességek összege, az idő pedig , ami belefér a rendelkezésre álló 30 percbe. |