Fişierul intrare/ieşire:matrice3.in, matrice3.outSursăAlgoritmiada 2010, Runda 4
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.7 secLimită de memorie10240 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Matrice3

Laura are o nouă matrice, de data aceasta binară, având N linii şi M coloane. Ca de obicei, curioasă din fire, Laura vă pune Q întrebări de forma: Care este latura maximă a unui pătrat ce conţine în interior doar 0 inclus complet în dreptunghiul cu colţul stânga-sus în (x1 y1) şi colţul dreapta-jos în (x2 y2)?

Cerinţă

Răspundeţi la întrebările Laurei.

Date de intrare

Pe prima linie a fişierului de intrare matrice3.in se află 3 numere întregi N, M şi Q cu semnificaţia din enunţ. Pe următoarele N linii se află câte M cifre din mulţimea {0, 1}, ce reprezintă matricea Laurei. Următoarele Q linii conţin câte 4 numere x1 y1 x2 y2 reprezentând colţurile dreptunghiului din fiecare întrebare.

Date de ieşire

Fişierul de ieşire matrice3.out va conţine Q linii, pe i-a linie (1 ≤ i ≤ Q) se află un singur număr întreg reprezentând răspunsul la a i-a întrebare.

Restricţii

  • 1 ≤ N, M ≤ 250
  • 1 ≤ Q ≤ 250 000
  • 1 ≤ x1 ≤ x2 ≤ N
  • 1 ≤ y1 ≤ y2 ≤ M
  • Pentru 30% din teste N, M ≤ 40 şi Q ≤ 250.
  • Pentru alte 30% din teste Q ≤ 100 000.

Exemplu

matrice3.inmatrice3.out
5 6 4
000101
010100
110001
010001
010000
1 1 3 3
1 1 5 6
2 2 4 5
4 2 5 2
1
3
2
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content