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

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

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

Indicii de rezolvare

Arată 1 categorii