infoarena informatica de performanta

Pariuri

Solutia 1: O(N * M + MAXT) - 80 puncte

Avand in vedere ca pentru 80% dintre teste, momentele de timp in care se pariaza erau ≤ 10⁶, puteam retine un vector auxiliar astfel:

• s[i] = suma de bani castigata in total de catre cei N oameni la momentul de timp i

Printr-o simpla parcurgere a perechilor de tipul (timp, bani) din fisierul de intrare, vom actualiza suma de bani astfel:

• s[timp] = s[timp] + bani;

De asemenea, este nevoie sa marcam undeva si momentele de timp in care s-au facut pariuri, pentru a sti exact ce momente de timp sa afisam. Astfel, parcurgand cu un contor i momentele de timp de la 1 la 10⁶, daca i este marcat, vom afisa i si s[i].

Solutia 2: O(N * M) - 100 puncte

Bazandu-ne pe acelasi principiu ca si cel anterior, constatam ca putem retina o tabela de dispersie / tabela hash pentru toate momentele de timp in care s-a pariat. Pentru fiecare moment de timp vom retine in hash valoarea de bani castigata de cei N oameni. In final, vom afisa doar momentele de timp care exista in hash.