Fişierul intrare/ieşire:secv2m.in, secv2m.outSursăAlgoritmiada 2009, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Secv2m

Ingrid are iar de rezolvat o problema cu secvente. Ea are doua siruri de numere intregi de lungime N si respectiv M. Ea vrea sa gaseasca doua subsecvente de lungime L, una din primul sir si cealalta din al doilea sir, Ai1, Ai2, ... , AiL si Bj1, Bj2, ... , BjL astfel incat max(Ai1 + Bj1, Ai2 + Bj2, ..., AiL + BjL) sa fie minim posibil.

Date de intrare

Fişierul de intrare secv2m.in va contine pe prima linie numerele N, M si L. A doua linie contine N numere intregi reprezentand primul sir, iar a treia linie contine M numere intregi reprezentand al doilea sir.

Date de ieşire

În fişierul de ieşire secv2m.out veti afisa pe prima linie valoarea minima ceruta. A doua linie va contine pozitia de inceput a primei subsecvente si pozitia de inceput a celei de a doua subsecvente separate printr-un spatiu. Daca exista mai multe solutii se va alege cea in care prima subsecventa are cea mai mica pozitie de inceput. Daca si in acest caz exista mai multe solutii se va alege solutia in care a doua subsecventa are cea mai mica pozitie de inceput.

Restricţii si precizari

  • 1 ≤ L ≤ N, M ≤ 2000
  • Toate numerele din fisierul de intrare sunt cuprinse intre 0 si 108

Exemplu

secv2m.insecv2m.out
5 7 3
4 3 4 2 2
3 1 3 2 5 3 2
5
3 2

Explicaţie

Subsecventele alese sunt : 4 3 4 2 2 si 3 1 3 2 5 3 2 (Atentie, se cer subsecvente si nu subsiruri).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content