Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tower.in, tower.out | Sursă | RMI 2016 |
| Autor | Alexandru Valeanu | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tower
Vă jucaţi un joc de apărare a turnurilor pe o grilă. Unele celule de pe grilă conţin roci prin care nu se trece, unele conţin inamici, iar altele sunt libere. Trebuie plasat un singur turn laser pe o celulă liberă. Odată plasat, turnul trage cu raze laser în direcţiile nord, sud, est şi vest. Raza îşi continuă drumul până iese din grilă sau loveşte o rocă, distrugând toţi inamicii de pe acea cale. Fiecare inamic distrus valorează un anumit punctaj. Scorul vostru final este suma valorilor fiecărui inamic distrus. Aflaţi scorul maxim posibil.
Date de intrare
Fişierul de intrare tower.in conţine două numere întregi pe prima linia, M şi N, reprezentând numărul de linii, respectiv de coloane al grilei. A doua linie conţine două numere întregi R şi E, reprezentând numărul de roci şi numărul de inamici. Următoarele R linii conţin o pereche de numere întregi l şi c, coordonatele liniei şi coloanei unei celule în care se află o rocă. Pe fiecare din cele E linii care succedă se găseşte un triplet l c s, reprezentând coordonatele celulei unui inamic şi numărul de puncte câştigate în urma distrugerii sale.
Date de ieşire
În fişierul de ieşire tower.out se va afişa un singur număr, valoarea maximă scorului final, posibilă pentru configuraţia dată.
Restricţii
- 1 ≤ M, N ≤ 1.000.000.000
- 1 ≤ R, E ≤ 100.000
- 1 ≤ l ≤ M şi 1 ≤ c ≤ N pentru toate coordonatele
- 1 ≤ s ≤ 10.000 pentru toate punctajele inamicilor
- O celulă conţine cel mult un inamic sau o rocă.
- Pentru 10% dintre teste M, N, R, E ≤ 1.000
- Pentru alte 20% dintre teste R, E ≤ 1.000
- Pentru alte 30% dintre teste R, E ≤ 30.000
Exemplu
| tower.in | tower.out |
|---|---|
| 10 10 3 6 2 3 1 5 6 3 5 2 40 5 5 10 5 6 30 1 3 20 2 5 50 3 3 10 | 90 |
Explicaţie
Amplasând turnul la coordonata (5, 3) se obţin 90 de puncte (40 + 10 + 10 + 30).
Dacă am fi plasat turnul la coordonata (5, 5) am fi obţinut mai multe puncte, însă turnul trebuie plasat pe o celulă liberă.
