Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Siruri

Adăugată de :
sorynsoo
Sursă :
XOR2011
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
400 ms
Limită memorie :
16384 kbytes

Fie două şiruri de lungime N de numere întregi a1, a2, ..., aN şi respectiv b1, b2, ..., bN. Alegând anumiţi indici 1 <= i1 < i2 < … < ik <= N, formăm sumele Sa = ai1 + ai2 + … + aik şi Sb = bi1 + bi2 + ... + bik.

 

Cerinţa

Să se determine suma Sa maximă care se poate obţine aleagând şirul de indici i1, i2, ..., ik astfel încât suma Sb să nu fie negativă.

 

Date de intrare

Fişierul de intrare conţine pe prima linie un număr natural N reprezentând lungimea şirurilor. Urmează N linii. Linia i+1 va conţine valorile ai şi bi separate printr-un spaţiu.

 

Date de iesire

Fişierul de iesire va conţine un singur număr natural reprezentând suma maximă Sa care se poate forma astfel încât suma Sb să nu fie negativă.

 

Restricţii şi precizări:

  • 3 <= N <= 1000
  • Valorile memorate în siruri sunt numere întregi cuprinse între -100 şi 100
  • Se garantează că pentru datele de intrare se poate obţine o soluţie validă cu Sb >= 0.

 

Exemple

  Date de intrare

  Date de iesire

Explicaţii

  3

  1 -5

  -4 8

  1 -1

  -2

  Şirul a este: 1 -4 1

  Şirul b este: -5 8 -1

  Suma maximă se obţine alegând toate numerele:

  Sa = 1 + (-4) + 1 = -2

  Sb = (-5) + 8 + (-1) = 3 >= 0

  Date de intrare

  Date de iesire

Explicaţii

  5

  -1 -3

  7 -3

  -1 8

  5 -11

  3 -1

  9

  Suma maximă se obţine alegând numerele de pe poziţiile 2, 3, 5:

  Sa = 7 + (-1) + 3 = 9

  Sb = -3 + 8 + (-1) = 4 >= 0


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !