Fişierul intrare/ieşire:emacs.in, emacs.outSursăOSEPI Baraj Seniori 2
AutorBogdan CiobanuAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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 ≤ i1 ≤ i2 ≤ N unde Ei1 = Ei2.

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 109+7.

Restricţii

  • 1 ≤ N ≤ 3 * 105
  • 1 ≤ Vi, Ei ≤ 109 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)

  • Ei = 1 pentru 1 ≤ i ≤ N

Subtask 3 (12 puncte)

  • Ei ≤ 20 pentru 1 ≤ i ≤ N

Subtask 4 (12 puncte)

  • Vi ≤ 20 pentru 1 ≤ i ≤ N

Subtask 5 (19 puncte)

  • N ≤ 5 * 104

Subtask 6 (38 de puncte)

  • Fără restricţii suplimentare.

Exemplu

emacs.inemacs.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?