Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | core2.in, core2.out | Sursă | Happy Coding 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Core2
Tocmai v-ati cumparat un procesor cu 2 core-uri, in speranta ca jocurile voastre preferate vor merge mult mai bine (dinamism mai ridicat, calitate a graficii mai buna, etc.). Fiind nerabdator sa testati noul procesor, vreti sa jucati toate cele N jocuri preferate cat mai curand. Jocurile sunt numerotate de la 1 la N si pentru fiecare joc i se cunoaste durata de joc di si satisfactia adusa si. Constatati repede ca, desi procesorul este mai avansat din punct de vedere tehnologic, jocurile preferate nu sunt in stare sa foloseasca complet noile capabilitati. Astfel, jocurile de la 1 la X pot fi rulate numai pe core-ul 1, iar jocurile X+1,...,N-1 pot fi rulate numai pe al doilea core. Jocul N este mai deosebit si necesita folosirea in paralel a ambelor core-uri. Stiind ca la fiecare moment de timp nu poate fi executat mai mult de un joc pe un core si ca nu va deranjeaza sa jucati cate doua jocuri in paralel (cate unul pe fiecare core), precum si ca aveti la dispozitie doar intervalul de timp [0,T] (dupa care trebuie sa mergeti la scoala), determinati ce jocuri veti juca astfel incat satisfactia totala obtinuta sa fie maxima. O constrangere suplimentara este data de faptul ca in intervalul de timp [T1,N,T2,N] vine in vizita cel mai bun prieten, pe care vreti sa-l impresionati; prin urmare, daca veti decide sa jucati jocul N (cel deosebit), o veti face doar in prezenta prietenului dumneavoastra (altfel spus, jocul N poate fi jucat doar intr-un interval de timp complet inclus in [T1,N,T2,N]). Un joc contribuie la satisfactia totala numai daca este jucat in intregime in intervalul de timp avut la dispozitie.
Date de intrare
Prima linie a fisierului de intrare core2.in contine 3 numere intregi: N, X si T. Urmatoarele N-1 linii contin cate doua numere intregi di si si, reprezentand durata jocului i si satisfactia provocata de acesta (a i-a dintre aceste linii corespunde jocului i). Ultima linie contine 4 numere intregi, separate prin cate un spatiu: dN, sN, T1,N, T2,N.
Date de iesire
In fisierul de iesire core2.out veti afisa un singur numar, reprezentand satisfactia totala maxima pe care o puteti obtine jucand jocuri in intervalul de timp pe care il aveti la dispozitie.
Restrictii
- 3 ≤ N ≤ 50
- 1 ≤ X ≤ N-2
- 1 ≤ di ≤ T ≤ 1000
- 0 ≤ T1,N < T2,N ≤ T
- 1 ≤ dN ≤ T2,N-T1,N
- 1 ≤ si ≤ 1000
- O data inceput, un joc trebuie jucat pana la sfarsit (altfel spus, daca alegeti sa jucati jocul i, acesta trebuie jucat pe durata unui interval de timp avand durata di)).
- Intervalul de timp in care jucati un joc i (1≤i≤N) trebuie sa fie complet inclus in intervalul [0,T]. Intervalul de timp in care jucati jocul N (daca il jucati) trebuie sa fie complet inclus in intervalul [T1,N,T2,N].
Exemplu
| core2.in | core2.out |
|---|---|
| 7 3 70 16 20 29 13 41 32 23 8 17 19 66 2 20 30 14 60 | 90 |
Explicatie
Jocurile 1, 2 si 3 pot fi rulate numai pe core-ul 1, iar jocurile 4, 5 si 6 pot fi rulate numai pe core-ul 2. Jocul 7 are nevoie de ambele core-uri in paralel. Satisfactia totala maxima egala cu 90 se obtine in felul urmator: veti juca jocul 1 in intervalul [0,16], jocul 7 in intervalul [17,37], jocul 2 in intervalul [37,68], jocul 5 in intervalul [0,17] si jocul 4 in intervalul [37,60]. Satisfactia totala este s1+s2+s4+s5+s7=20+13+8+19+30=90. Observati ca in intervalul [17,37] (cand jucati jocul 7), niciun alt joc nu este rulat pe nici unul din cele 2 core-uri, acestea fiind folosite exclusiv de jocul 7.
