Fişierul intrare/ieşire:bcrc.in, bcrc.outSursăStelele Informaticii 2006, clasele 9-10
AutorMugurel Ionut AndreicaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test1.05 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Bcrc

Gigel se afla intr-un labirint alcatuit din N camere, numerotate de la 1 la N, asezate in cerc. Din camera K (1 < K < N) el poate trece in camerele K - 1 si K + 1. Din camera 1 poate trece in camerele 2 si N, iar din camera N poate trece in camerele N - 1 si 1.

Initial (la momentul de timp 0), Gigel se afla in camera 1. In fiecare moment de timp, Gigel poate decide sa ramana in camera in care se afla sau sa se mute intr-una din cele 2 camere invecinate. Deplasarea dintr-o camera intr-una din camerele invecinate dureaza o unitate de timp. Astfel, daca la momentul T Gigel decide sa se deplaseze intr-o camera vecina, el va ajunge in camera respectiva la momentul T + 1.

Din cand in cand, in unele camere apar cutii continand fiecare un anumit numar de bomboane (posibil diferit de la o cutie la alta). Sa presupunem ca o cutie apare in camera X la momentul de timp T. Daca Gigel se afla la momentul T in camera X (sau intra in acea camera chiar la momentul T), atunci el ia cutia si mananca toate bomboanele din ea. In caz contrar, Gigel nu va putea manca nici o bomboana din cutie, deoarece aceasta va disparea pana la momentul T + 1.

Cerinta

Cunoscand numarul de camere din labirint si momentele de timp la care apar cutiile cu bomboane, determinati care este numarul maxim de bomboane pe care le poate manca Gigel. Numarul de bomboane pe care le mananca Gigel este suma numerelor de bomboane din fiecare cutie pe care o ia.

Date de intrare

Prima linie a fisierului bcrc.in contine doua numere intregi, separate printr-un spatiu: N si M, reprezentand numarul de camere din labirint, respectiv numarul de cutii. Fiecare din urmatoarele M linii contine cate 3 numere intregi, separate prin cate un spatiu: T, C si B. T reprezinta momentul la care apare cutia. C reprezinta numarul camerei in care apare cutia. B reprezinta numarul de bomboane pe care le contine cutia.

Cutiile sunt date in fisierul de intrare in ordine crescatoare a momentelor de timp la care apar.

Date de iesire

In fisierul bcrc.out veti afisa un singur numar, reprezentand numarul maxim de bomboane pe care le poate manca Gigel.

Restrictii

  • 3 ≤ N ≤ 2 048
  • 0 ≤ M ≤ 50 000
  • Pentru fiecare cutie:
    • 1 ≤ T ≤ 1 000 000 000
    • 1 ≤ C ≤ N
    • 1 ≤ B ≤ 9 999
  • Pot aparea mai multe cutii la acelasi moment de timp, in camere diferite (dar nu in acelasi moment de timp si in aceeasi camera)
  • 30% din fisierele de test vor avea M ≤ 5 000
  • 30% din fisierele de test vor avea N ≤ 256

Exemplu

bcrc.inbcrc.out
8 4
2 7 9
3 5 999
10 2 12
10 1 10
21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content