Fişierul intrare/ieşire:valentin.in, valentin.outSursăProsoft@NT 2016, Clasa a 9-a
AutorZoltan SzaboAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.invalentin.outExplicatie
1
4
3 -3 0 -3
0
v=1, se rezolvă prima cerinţă, adică:
suma maximă pară a unui subşir este 0.
valentin.invalentin.outExplicatie
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?