Fişierul intrare/ieşire:3max.in, 3max.outSursăLot Arad 2011
AutorAndrei ParvuAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

3max

După ce a făcut profit lucrând la fabrica de lângă Arad, Dorel şi-a schimbat din nou locul de muncă şi acum s-a angajat la o companie ce produce batoane energizante.

Până în acest moment compania a produs N batoane care, aflându-se pe banda de producţie, sunt dispuse în linie. Pentru fiecare baton se ştie numărul de calorii pe care o persoană le câştigă dacă mănâncă acel baton (din pacate, compania nu este specializată în producerea de batoane energizante şi de accea pot exista şi batoane pentru care numărul de calorii câştigate este negativ).

Dorel doreşte să se înfrupte cu o parte din batoane, dar pentru a nu stârni suspiciuni, a hotărât că va alege trei subsecvenţe disjuncte din secventa de N batoane pe care le va mânca. Notăm aceste subsecvenţe cu [i1, j1], [i2, j2], [i3, j3], (1 ≤ i1 ≤ j1 < i2 ≤ j2 < i3 ≤ j3 ≤ N).

Desigur, menirea batoanelor energizante este de a avea cât mai multe calorii, aşadar Dorel doreşte ca suma caloriilor produse de batoanele din cele trei subsecvenţe să fie cât mai mare. Totusi, Dorel are nişte constrângeri privind subsecvenţa din mijloc. Aceasta trebuie să fie inclusă într-un anumit interval [x, y] (aşadar, x ≤ i2 ≤ j2 ≤ y).

Cerinta

Fiind date M intervale de forma [x, y] trebuie să afişaţi numărul maxim de calorii pe care le poate obţine Dorel, dacă alege trei subsecvenţe conform regulilor de mai sus.

Date de intrare

Pe prima linie a fişierului 3max.in se va afla N, numărul de batoane şi M, numărul de întrebări. Următoarea linie conţine N numere întregi, al i-lea din aceste numere reprezentând numărul de calorii al batonului i. Următoarele M linii conţin fiecare două numere întregi x, y, reprezentând o constrângere pentru subsecvenţa din mijloc.

Date de ieşire

Cele M linii ale fişierului 3max.out vor conţine M numere naturale, răspunsurile la cele M întrebări.

Restricţii

  • 1 ≤ N ≤ 50 000
  • 1 ≤ M ≤ 100 000
  • 1 ≤ x ≤ y ≤ N
  • Numărul de calorii pe care îl conţine un baton este cuprins în intervalul [-106, 106].
  • Atenţie! Daca o subsecvenţa aleasa are suma negativă, Dorel considera ca are suma 0.
  • Atenţie! Dorel este obligat sa aleaga 3 subsecvente, iar daca nu va putea alege, se va afisa valoarea 0.
  • O subsecvenţă a unui şir se defineşte ca fiind o submulţime de elemente ale şirului aflate pe poziţii consecutive.
  • Celelalte două subsecvenţe se pot intersecta cu intervalul [x, y] atata timp cât respectă toate proprietăţile.

Exemplu

3max.in3max.outExplicatie
7 2
2 -5 6 3 2 -4 3
2 3
3 6
13
16
Se aleg subsecvenţele [1, 1], [3, 3], [4, 5], respectiv [1, 1], [3, 5], [7, 7].
4 1
-10 2 3 -10
1 4
5
Se aleg subsecvenţele [1, 1], [2, 3], [4, 4]. Cum subsecventele [1, 1] si [4, 4] au suma negativa,
Dorel le considera ca avand suma 0, deci rezultatul este 0 + 5 + 0 = 5.
3 1
-1 -2 -3
2 2
0
Se aleg subsecvenţele [1, 1], [2, 2], [3, 3].
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content