Fişierul intrare/ieşire:plantatie.in, plantatie.outSursăpreONI 2007, Runda 2
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Plantatie

Zaharel si cu Nargy au cumparat recent o plantatie de tutun de marime N x N metri. Dupa o analiza complexa, ei au calculat pentru fiecare bucata de 1 × 1 metri productivitatea ei, adica cantitatea de tutun pe care o obtin intr-o zi plantand tutun pe acea bucata.
Pentru a mari productivitatea ei vor sa analizeze doar anumite bucati patratice din intreaga plantatie. Pentru asta ei si-au pus M intrebari de forma: "Care este bucata 1 × 1 de productivitate maxima dintr-un patrat cu coltul stanga-sus pe linia i si coloana j si latura k?". Scrieti un program sa-i ajute pe cei doi sa raspunda la aceste intrebari.

Date de intrare

Prima linie a fisierului plantatie.in va contine numerele naturale N si M separate prin cate un spatiu. Urmatoarele N linii vor contine cate N numere naturale separate prin spatii, reprezentand productivitatea bucatilor 1 × 1 din plantatie. Urmatoarele M linii vor contii triplete de numere i j k, reprezentand intrebarile pe care le au cei doi.

Date de iesire

Fisierul de iesire plantatie.out contine M linii, reprezentand raspunsurile la intrebari, in ordinea din fisierul de intrare.

Restrictii

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ 75.000
  • Productivitatea unei bucati din plantatie este un numar natural din intervalul [0, 1.000.000.000]
  • Liniile si coloanele plantatiei sunt numerotate cu numere de la 1 la N
  • Toate intrebarile vor reprezenta patrate aflate complet in interiorul plantatiei

Exemplu

plantatie.inplantatie.out
8 3
7 8 0 0 0 0 5 5
0 0 0 0 0 0 5 5
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 2 3 4
0 0 0 0 5 6 7 8
0 0 0 0 9 10 11 12
1 1 1 1 14 15 16 17
1 1 8
4 5 3
2 2 6
17
7
11
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content