Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2016-11-27 15:13:51.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:tower.in, tower.outSursăRMI 2016
AutorAlexandru ValeanuAdăugată debciobanuBogdan Ciobanu •bciobanu
Timp execuţie pe test0.75 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.intower.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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?