Fişierul intrare/ieşire:smaralde.in, smaralde.outSursăMarele Premiu (PACO)
AutorSmaranda DinuAdăugată deStelarCFSanduleac Vlad StelarCF
Timp execuţie pe test1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Smaralde

Radu a cumpărat mine de smarald în Columbia.
Ele sunt aşezate pe n linii si m coloane. Cunoscând profitul pe care l-ar obţine exploatând fiecare mină, el vrea să extragă smaraldele folosind un dispozitiv care poate mina doar porţiuni de formă dreptunghiulară.
Din când în când, trimite pe teren cercetători care reevaluează profitul obţinut în minele de pe o anumită coloană.

Radu vă roagă să creaţi un program care să efectueze două tipuri de operaţii:

  • 1 – afişează i1, j1, i2, j2, smax coordonatele colţului stânga-sus, respectiv dreapta-jos şi suma valorilor minelor din cel mai profitabil dreptunghi
  • 2 col val – actualizează profiturile minelor de pe coloana col, adăugând val la fiecare dintre ele

Date de intrare

Pe prima linie a fişierului smaralde.in se găsesc două numere naturale n şi m, cu semnificaţia din enunţ. Următoarele n linii conţin câte m numere întregi, reprezentând profitul iniţial pentru fiecare mină. În continuare se află numărul natural Q, numărul de operaţii pe care le va efectua programul şi Q linii pe care sunt operaţiile descrise în enunţ.

Date de ieşire

În fişierul smaralde.out, pentru fiecare operaţie de tip 1, se va găsi o linie cu valorile i1, j1, i2, j2, smax separate printr-un spaţiu, cu semnficaţia din enunţ. Dacă nu există niciun dreptunghi de sumă strict pozitivă, se va afişa 0.

Restricţii

  • 1 ≤ n, m ≤ 100
    ( 1 ≤ Q ≤ 50
  • 1 ≤ col ≤ m; -1000 ≤ val ≤ 1000
  • -1000 ≤ profitul iniţial pentru o mină ≤ 1000
  • Dacă sunt mai multe dreptunghiuri de sumă maximă, se va alege cel cu i1 minim. Dacă sunt mai multe astfel de dreptunghiuri, se va alege cel cu i2 minim. Dacă sunt mai multe astfel de dreptunghiuri, se va alege cel cu j1 minim. Daca sunt mai multe astfel de dreptunghiuri, se va alege cel cu j2 minim.
  • Pentru 30% din teste, 1 ≤ n, m ≤ 50.

Exemplu

smaralde.insmaralde.out
4 3
-5 4 2
1 2 3
-2 -1 1
-3 -1 1
4
1
2 1 6
2 3 -3
1
1 2 2 3 11
1 1 4 2 19

Explicaţie

După prima operaţie de tip 2, se modifică prima coloană:
1 4 2
7 2 3
4 -1 1
3 -1 1
După a doua operaţie de tip 2, se modifică a treia coloană:
1 4 -1
7 2 0
4 -1 -2
3 -1 -2

Trebuie sa te autentifici pentru a trimite solutii. Click aici