Laiko ribojimas: 1s
Atminties ribojimas: 64MB
Duomenų failas: upe.in
Rezultatų failas: upe.out
Užteršta upė
Padidėjus pesticidų naudojimui, kai kurios upės buvo taip užterštos, kad net vandens gyvūnai nebegalėjo jose gyventi.
Varlė Fredas gyvena prie vienos tokios upės. Jis nori susitikti su draugu. Todėl jam reikia patekti į kitą upės krantą ir po to grįžti. Deja, upė labai užteršta ir Fredas negali ja plaukti.
Laimei, upėje, kurios plotis yra D centimetrų, yra N tiesia linija išsidėsčiusių akmenų. Akmenys yra dviejų dydžių. Maži akmenys pradės skęsti vos tik Fredas ant jų užšoks, todėl jais pasinaudoti gali tik vieną kartą. Tuo tarpu, dideli akmenys laikosi tvirtai ir ant jų Fredas gali užšokti kiek nori kartų.
Suplanuokite Fredo maršrutą per akmenis taip, kad ilgiausias šuolis būtų kuo trumpesnis.
Pradiniai duomenys
Pirmoje eilutėje yra sveikieji skaičiai N () ir D (). Tolesnėse N eilučių aprašomi akmenys. Kiekvienoje eilutėje yra raidė 'D' arba 'M', nusakanti akmens dydį (Didelis arba Mažas), ir sveikas skaičius M () - akmens atstumas nuo Fredo kranto. Akmenys pateikti M didėjimo tvarka. Nebus dviejų akmenų su vienodais M.
Rezultatai
Vienintelėje eilutėje įrašykite vieną skaičių - ilgiausio šuolio atstumą.
Pavyzdys
Duomenys | Rezultatai |
---|---|
3 10 D 3 M 6 M 8 |
5 |