Editing 2056 - Popcorn (section)

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2056 Popcorn
T_POCNIRE = 0
T_ARDERE = 1
CANTITATE = 2


def conditii(n_tipuri, n_pungi, tipuri_floricele):
    for tip in tipuri_floricele:
        if not 1 <= tip[T_POCNIRE] < tip[T_ARDERE] <= 200_000:
            return False

    if sum([tip[CANTITATE] for tip in tipuri_floricele]) > 10**9:
        return False

    if not 1 <= n_pungi <= n_tipuri <= 200_000:
        return False

    x = [tip[T_ARDERE] for tip in tipuri_floricele]
    x.append(n_tipuri)

    x_max = max(x)

    if not n_pungi <= x_max <= 50_000:
        return False

    return True


def popcorn(n_tipuri, n_pungi, floricele):
    # Inițializăm o listă bidimensională pentru a stoca cantitatea de popcorn care poate fi preparată pentru fiecare
    # tip de popcorn și pentru fiecare pas de timp

    # Lista are n_tipuri rânduri și 50,000 coloane, deoarece fiecare tip de popcorn poate fi preparat pentru maxim
    # 50,000 de pași de timp
    nr = [[0 for j in range(50_000)] for i in range(n_tipuri)]
    for i in range(n_tipuri):
        # Pentru fiecare tip de popcorn, parcurgem pașii de timp când popcorn-ul poate fi preparat
        # (de la T_POCNIRE la T_ARDERE)
        for k in range(floricele[i][T_POCNIRE], floricele[i][T_ARDERE]):
            if k < floricele[i][T_ARDERE]:
                nr[i][k] = floricele[i][CANTITATE]

    # Inițializăm o altă listă bidimensională cu n_tipuri+1 rânduri și n_pungi+1 coloane
    # Fiecare element din listă va stoca cantitatea maximă de popcorn care poate fi pusă în j pungi
    # folosind primele i tipuri de popcorn
    dinamic = [[0 for j in range(n_pungi+1)] for i in range(n_tipuri+1)]
    for i in range(1, n_tipuri+1):
        for j in range(1, n_pungi+1):
            for k in range(j, -1, -1):
                # Calculăm cantitatea maximă de popcorn care poate fi pusă în j pungi folosind primele i tipuri de popcorn,
                # bazat pe cantitatea de popcorn care poate fi preparată pentru fiecare tip și pas de timp, stocată în lista "nr"
                dinamic[i][j] = max(dinamic[i][j], dinamic[i-1][k] + sum(nr[i-1][:j-k]))

    # Printăm cantitatea maximă de popcorn care poate fi pusă în pungi, 
    # care este valoarea din colțul din dreapta jos al tabelei "dinamic"
    print(max(dinamic[-1]))


if __name__ == "__main__":
    n_tipuri, n_pungi = [int(x) for x in input().split(" ")]

    floricele = []

    for i in range(n_tipuri):
        timp_pana_la_pocnire, timp_pana_la_ardere, cantitate = [int(x) for x in input().split()]
        floricele.append([timp_pana_la_pocnire, timp_pana_la_ardere, cantitate])

    if not conditii(n_tipuri, n_pungi, floricele):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        popcorn(n_tipuri, n_pungi, floricele)

</syntaxhighlight>