Fișierul intrare/ieșire orar.in, orar.out Sursă Pregatire Clasa a 7-a
Autor Teodor Plop Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.65 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Orar

Datorita apropierii Olimpiadei de Informatica, Gigel trebuie sa lucreze din greu, atat pentru a fi sigur de succesul sau, cat si pentru a isi impresiona parintii.

Acesta isi face un orar de lucru in care, in curs de N zile, el lucreaza in ziua i, un interval egal cu a[i] unitati de timp. La finalul celor N zile insa, parintii ii pun acestuia Q intrebari de tipul:

  • Cat timp ai “pierdut” incepand cu ziua x, pana in ziua y, lucrand la informatica, inclusiv x si y?

Fiind siret, acesta se gandeste parintii vor fi foarte multumiti de el, daca suma tuturor raspunsurilor ce corespund acestor intrebari va fi cat mai mare. Asa ca se gandeste sa modifice timpii sai de lucru din fiecare zi prin urmatoarea operatie:

  • Interschimba numarul unitatilor de timp lucrate in ziua i cu cele din ziua j.

Mai precis, se doreste o rearanjare a sirului initial, astfel incat suma raspunsurilor date de Gigel sa fie maxima.

Curios daca planul lui malefic merge intocmai, acesta va intreaba care este suma maxima a tuturor raspunsurilor la intrebarile parintilor, dupa efectuarea operatiilor prezentate mai sus?

Date de intrare

Fișierul de intrare orar.in contine pe prima linie numarul natural N, iar pe urmatoarea linie N numere naturale din sirul a[i]. Pe linia a treia se va afla numarul natural Q, iar pe urmatoarele Q linii se vor afla cate doua numere naturale x si y.

Date de ieșire

În fișierul de ieșire orar.out se va gasi un singur numar natural, reprezentand suma maxima ce poate fi obtinuta prin adunarea raspunsurilor, dupa efectuarea operatiilor.

Restricții

  • 1 ≤ N, Q ≤ 200.000
  • 1 ≤ a[i] ≤ 200.000
  • 1 ≤ x ≤ y ≤ N

Exemplu

orar.in orar.out Explicatie
6
5 10 9 8 7 8
3
1 6
4 5
4 4
76
Suma maxima se poate obtine prin urmatoarea aranjare a sirului initial: 5 7 8 10 9 8,
si anume 5 + 7 + 8 + 10 + 9 + 8 + 10 + 9 + 10 = 76.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii