Fișierul intrare/ieșire | smaralde.in, smaralde.out | Sursă | Marele Premiu (PACO) |
---|---|---|---|
Autor | Smaranda Dinu | Adăugată de | Sanduleac Vlad • StelarCF |
Timp de execuție pe test | 1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.in | smaralde.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