Fişierul intrare/ieşire:silvania.in, silvania.outSursăAlgoritmiada 2019 Runda Finala
AutorAdrian Budau, Eugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test1.6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Silvania

Silvania, in latina, inseamna "zona impadurita". Problema aceasta este despre paduri

Bogdi din Silvania, taietorul de lemne, a dat-o pe ecologie. El a decis sa inconjoare padurea cu un gard, ca alti taietori de lemne sa nu o mai atace -- dar nestiind cum sa faca orice in afara de a taia lemne, gardul va fi construit din lemnul padurii.
Padurea din Silvania este formata de un numar de arbori, fiecare cu o anumita cantitate de lemn, pusi in linie, la diverse pozitii. Bogdi poate taia orice submultime de arbori, si din acest act strange o cantitate de lemn egal cu suma cantitatilor de lemn ale arborilor taiati. Bogdi vrea neaparat ca, dupa aceasta taiere, sa aiba suficient lemn pentru a inconjura restul arborilor cu un singur gard -- adica sa aiba o cantitate de lemn mai mare sau egala cu distanta dintre primul si ultimul arbore ramas netaiat. Ajutati-l sa gaseasca numarul minim de arbori pe care trebuie sa ii taie.

Date de intrare

Fişierul de intrare silvania.in va contine, pe primul rand, numarul N de teste.
Urmeaza N numere pe urmatorul rand, cantitatile de lemn ale arborilor.
Urmeaza N numere pe urmatorul rand, pozitiile arborilor.

Date de ieşire

În fişierul de ieşire silvania.out se va afisa un singur numar natural, numarul minim de arbori ce trebuie taiati.

Restricţii

  • 1 ≤ N ≤ 5.000
  • 1 ≤ cantitatea de lemn a unui arbore ≤ 1.000.000.000
  • 1 ≤ pozitia unui arbore ≤ 1.000.000.000
  • Pozitiile arborilor sunt distincte
  • Pentru teste in valoare de 10 puncte 1 ≤ N ≤ 100
  • Pentru teste in valoare de inca 30 de puncte 1 ≤ N ≤ 1.000
  • Fiecare din aceste subtask-uri (cele 2 de mai sus, si cel in valoare de 60 de puncte cu 1 ≤ N ≤ 5.000) este impartit in 2 subtask-uri mai mici.
    • Prima jumatate din punctajul pe subtask este pentru teste in care fiecare copac este unic. Mai exact, nu se gasesc doi copaci diferiti care au exact aceeasi cantitate de lemn.
    • A doua jumatate din punctajul pe subtask este pentru teste care nu mai au nico restritie suplimentara.

Exemplu

silvania.insilvania.out
5
2 3 2 1 2
4 5 1 3 10
2

Explicaţie

Exista mai multe modalitati de a taia copacii si a construi gardul. Una din ele:

  • Se taie al doilea copac (pentru a obtine 3 lemn) si ultimul copac (pentru inca 2 lemn).
  • Se construieste gard de la pozitia 1 la pozitia3 4.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?