Fişierul intrare/ieşire:	emacs.in, emacs.out	Sursă	OSEPI Baraj Seniori 2
Autor	Bogdan Ciobanu	Adăugată de	Matteo Verzotti •Matteoalexandru
Timp execuţie pe test	1 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Emacs

Martie 1993,

Tradiţia făcea ca micul rms işi petrecea iar timpul în editorul de text mai bun. Observând obsesia îngrijorătoare, apropiaţiilor le mai scăpară vorbe: „Mai ieşi şi tu din editorul ălă, ceilalţi copii de vârsta ta mai fac şi altele, mai stau pe telefonul mobil, mai intră in browser!". rms nu consideră că e vreo problemă, nici ceilalţi de vârsta lui nu ar fi putut ieşi din editor, pentru că nu ştiau comanda.
Era însă o zi specială, de Sfântul IGNUcius, rms nu ar fi conceput să se ocupe cu treburi superficiale. Discuţiile aprinse pe email cu ceilalţi pedanţi păreau să nu aibe vreun deznodământ şi îi captaseră întreaga atenţie. Urma să prezinte cea mai noua funcţionalitate la care a lucrat, M-x compune-o-problema-random şi rezultatul (îndrăznim să zicem, pe măsură!), obţinut.

Se consideră două şiruri de N numere naturale, V şi E. Se cere suma valorilor maxime din V pentru toate subsecvenţele determinate de capetele 1 ≤ i₁ ≤ i₂ ≤ N unde E_i1 = E_i2.

Date de intrare

Fişierul de intrare emacs.in pe prima linie se află numărul de elemente N. Pe fiecare dintre următoarele două linii se află N numere naturale, reprezentând elementele şirului V, respectiv E.

Date de ieşire

În fişierul de ieşire emacs.out pe prima linie se va afişa rezultatul cerut modulo 10⁹+7.

Restricţii

• 1 ≤ N ≤ 3 * 10⁵
• 1 ≤ V_i, E_i ≤ 10⁹ pentru 1 ≤ i ≤ N
• O subsecvenţă este un subşir format din elemente cu indici consecutivi.

Subtask 1 (8 puncte)

• N ≤ 2 000

Subtask 2 (11 puncte)

• E_i = 1 pentru 1 ≤ i ≤ N

Subtask 3 (12 puncte)

• E_i ≤ 20 pentru 1 ≤ i ≤ N

Subtask 4 (12 puncte)

• V_i ≤ 20 pentru 1 ≤ i ≤ N

Subtask 5 (19 puncte)

• N ≤ 5 * 10⁴

Subtask 6 (38 de puncte)

• Fără restricţii suplimentare.

Exemplu

emacs.in	emacs.out
5 5 29 3 28 30 9 8 9 9 8	211

Explicaţie

Subsecvenţele care contribuie la răspuns sunt cele unde capetele au valori egale în E. În cazul de faţă, tuplurile care conţin cele două capete şi valoarea maxima din V sunt (1, 1, 5), (1, 3, 29), (1, 4, 29), (2, 2, 29), (2, 5, 30), (3, 3, 3), (3, 4, 28), (4, 4, 28), (5, 5, 30).
Aceste valori însumate dau 211.

Cum se trimit solutii?