ID #123 · Colecția InfoAs · Operatori și expresii

Problema Printre noi

Fascinați de un joc popular pe care îl joacă un fiecare seară, un grup de prieteni se inspiră după acesta și creează un joc similar, numit _Printre noi_. Jocul se desfășoară astfel: grupul de `n` prieteni se așează circular (ultimul și primul prieten sunt vecini), iar fiecare persoană alege un număr natural `a<sub>i</sub>` împreună cu o (non)culoare, alb sau negru. Cineva este ales la întâmplare și devine, fără să știe ceilalți, _hoțul jocului_. Rolul hoțului este de a alege câteva persoane din grup așezate pe poziții consecutive astfel încât să maximizeze suma numerelor persoanelor care au ales culoarea negru și să minimizeze suma numerelor persoanelor care au ales culoarea alb. Hoțul trebuie să calculeze răspunsul optim cât de rapid posibil, iar dacă celelalte persoane se prind între timp cine este, atunci acesta pierde. Considerăm că prietenii sunt numerotați de la `1` la `n`. Deoarece prietenii sunt așezați în cerc, secvența poate să înceapă de pe o anumită poziție, să conțină persoanele `n` și `1` și să continue de la începutul șirului. ## Cerință Paul devine hoț pentru mai multe runde și vrea să calculeze cât de rapid răspunsurile, spre a putea câștiga rundele. Din acest motiv, te roagă pe tine să calculezi cât de repede posibil care ar fi scorul maxim pe care l-ar putea obține. Scorul se obține adunând numerele _negre_ și scăzând numerele _albe_ ale secvenței alese. ## Date de intrare Fișierul de intrare `printre-noi.in` conține pe prima linie numărul natural `n`. Pe a doua linie se află cele `n` numere naturale alese de fiecare prieten în parte. Pe a treia linie se află `n` numere, `0` sau `1`, în funcție de culoarea aleasă de fiecare persoană în parte din grup. Dacă numărul este `0`, atunci culoarea este alb, altfel, culoarea este negru. Numerele de pe fiecare linie în parte sunt separate prin câte un spațiu. ## Date de ieșire Fișierul de ieșire `printre-noi.out` va conține un singur număr natural reprezentând scorul maxim posibil care se poate obține dintr-o secvență a șirului. Atenție, șirul este circular! ## Restricții și precizări * `1 ≤ n ≤ 100.000` * `1 ≤ fiecare număr ales ≤ 1.000.000.000` * Cel puțin o persoană va alege culoarea negru