Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | lupu.in, lupu.out | Sursă | preONI 2006 Runda Finala |
Autor | Adrian Diaconu | Adăugată de | |
Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Lupul Urias si Rau
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
Link: [1]File-List
Lupul Urias si Rau
Lupul urias si rau isi doreste sa se poata juca cu prietenele sale oitele mici si pufoase. In calea fericirii sale sta insa ciobanasul Eduard care decide sa nu-l lase pe lup sa se joace cu toate oile sale, il lasa sa aleaga doar cateva. Lupul se afla intr-un punct fix pe pajiste, iar oile stau la diferite distante fata de el. Alegerea oilor se face in mai multe etape. Lupul urias si rau alege o oaie aflata la o distanta de maxim X si in acel moment toate celelalte oi se vor indeparta (la cerintele ciobanasului Eduard) cu distanta L fata de lup. Pentru fiecare oaie se cunoaste cantitatea de lana pe care o are, iar lupul isi doreste ca suma cantitatilor de lana pentru oile alese sa fie cat mai mare (ca sa fie cat mai pufoase).
Cerinta
Ajutati-l pe lupul urias si rau sa aleaga oile astfel incat sa aiba cat mai multa lana.
Date de Intrare
Prima linie a fisierului de intrare lupu.in contine trei numere intregi N , X si L reprezentand numarul de oi, distanta maxima de la care lupul poate alege oi si distanta cu care se daparteaza oile de lup dupa fiecare alegere. Pe urmatoarele N linii se afla cate doua numere intregi D si A reprezentand distanta initiala si cantitatea de lana a fiecarei oi.
Date de Iesire
In fisierul lupu.out veti afisa un singur numar intreg S, reprezentand cantitatea maxima de lana pe care o poate aduna lupul de la oile alese.
Restrictii si precizari
o 1 <= N <= 100.000
o Pentru 40% din teste N <= 1000
o Toate numerele din fisierul de intrare sunt intregi din intervalul [0, 2^31-1]
Exemplu
lupu.in lupu.out
10 6 2 54
1 13
4 14
4 3
6 7
0 7
5 16
3 16
4 10
4 18
3 16
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/lupu/enunt.files/filelist.xml