Fișierul intrare/ieșire goldmine2.in, goldmine2.out Sursă Simulare OJI Clasa a 9-a
Autor Teodor Plop Adăugată de avatar teodor94 Teodor Plop • teodor94
Timp de execuție pe test 0.35 sec Limită de memorie 6144 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Gold Mine 2 (clasa a 9-a)

Se dă o hartă a unei mine de aur sub forma unei matrice cu N linii și M coloane:
  • Fiecare element A[i][j] reprezintă cantitatea de aur care poate fi extrasă din acea zonă.
  • Liniile reprezintă adâncimea (linia 1 este la suprafață, linia N este cel mai adânc).
Compania primește Q contracte. Fiecare contract este specificat prin două valori: (K, G).
  • K: Numărul maxim de excavatoare disponibile. Putem alege cel mult K coloane distincte în care să săpăm.
  • G (Gold): Cantitatea totală minimă de aur care trebuie extrasă.

Pentru a extrage aurul, excavatoarele sapă vertical. Din rațiuni de eficiență energetică, se dorește ca adâncimea maximă la care ajunge oricare dintre excavatoare să fie minimă. Practic, căutăm o adâncime limită H, astfel încât săpând în K coloane “profitabile” până la linia H, suma totală a aurului colectat să fie cel puțin G.

Cerință

Pentru fiecare dintre cele Q contracte, determinați adâncimea minimă H necesară. Dacă nu se poate colecta cantitatea G nici săpând până la fundul minei (linia N) cu toate cele K excavatoare, se va afișa -1.

Date de intrare

Fișierul de intrare goldmine2.in conține pe prima linie numerele naturale N, M și Q. Pe următoarele N linii se găsesc câte M numere naturale, reprezentarea minei de aur. Pe următoarele Q linii se găsesc câte două numere naturale K și G, datele de contract.

Date de ieșire

Fișierul de ieșire goldmine2.out va conține Q linii, pe fiecare linie aflându-se răspunsul la câte un contract. Dacă contractul nu poate fi satisfăcut, se va afișa -1.

Restricții

  • 1 ≤ N ≤ 1.000
  • 1 ≤ M ≤ 250
  • 1 ≤ A[i][j] ≤ 1.000, cantitățile de aur
  • 1 ≤ Q ≤ 500.000
  • 1 ≤ K ≤ M
  • 1 ≤ G ≤ 250.000.000

Exemplu

goldmine2.in goldmine2.out Explicație
3 4 4
2 1 5 3
4 2 6 1
1 8 1 5
2 10
3 13
1 13
4 10
 2
2
-1
1
 Putem săpa coloana 3 cu un singur excavator, pe adâncime 2
Putem săpa coloana 3 pe adâncime 2 și coloana 1 pe adâncime 1
Nu avem cum să obținem cel puțin 13 aur cu un singur excavator
Putem săpa cu toate excavatoarele la adâncime 1

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii