Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | valentin.in, valentin.out | Sursă | Prosoft@NT 2016, Clasa a 9-a |
| Autor | Zoltan Szabo | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Valentin
Valentin şi Valentina sunt gemeni. De ziua lor au primit de la părinţi un şir format din n numere întregi. Valentin a hotărât să păstreze doar câteva elemente ale şirului, astfel ca suma acestora să fie maximă şi mai mult de atât, să fie un număr par, pentru că, fiind un frate bun, doreşte să dea jumătate din sumă Valentinei.
Concentrându-se asupra problemei, el vrea să primească răspuns la două întrebări:
1. Ce valoare are suma maximă pară unui subşir?
2. Câte subşiruri distincte există cu suma maximă pară?
Date de intrare
Fişierul de intrare valentin.in conţine pe prima linie un număr natural v. Pentru toate testele de intrare, numărul v poate avea doar valoarea 1 sau 2.
A doua linie a fişierului conţine numărul natural n. Următoarea linie conţine cele n elemente ale şirului, numere întregi separate prin spaţii.
Date de ieşire
Dacă valoarea lui v este 1, se va rezolva numai punctul 1 din cerinţă.
În acest caz în fişierul de ieşire valentin.out se va scrie un singur număr întreg ce reprezintă valoarea maximă a sumei pare a unui subşir.
Dacă valoarea lui v este 2, se va rezolva numai punctul 2 din cerinţă.
În acest caz, în fişierul de ieşire valentin.out se va scrie un singur număr natural ce reprezintă numărul subşirurilor de sumă maximă pară.
Restricţii
- 1 ≤ n ≤ 600 000;
- -1 000 000 000 ≤ elementele şirului ≤ 1 000 000 000;
- suma maximă poate fi şi negativă;
- un subşir conţine cel puţin un element;
- două subşiruri se consideră distincte dacă diferă prin cel puţin o poziţie de element;
- pentru toate testele rezultatele se vor încadra în tipul long long (C/C++), respectiv int64 (Pascal) ;
- pentru 50% din teste valorarea lui v = 1, alte pentru alte 50% din teste valoarea lui v = 2;
- pentru 30% din teste valoarea lui n ≤ 21
- pentru 45% din teste valoarea lui n ≤ 1000
- pentru 60% din teste valoarea lui n ≤ 50000
Exemplu
| valentin.in | valentin.out | Explicatie |
|---|---|---|
| 1 4 3 -3 0 -3 | 0 | v=1, se rezolvă prima cerinţă, adică: suma maximă pară a unui subşir este 0. |
| valentin.in | valentin.out | Explicatie |
|---|---|---|
| 2 4 3 -3 0 -3 | 5 | v=2, se rezolvă a doua cerinţă, adică: avem 5 subşiruri cu suma maximă pară: 1. (a1, a2) → 3-3=0 2. (a1, a2, a3) → 3-3+0=0 3. (a1, a3, a4) → 3+0-3=0 4. (a1, a4) → 3-3=0 5. (a3) → 0=0 |
