Cod sursa(job #2723502)

Utilizator mariusn01Marius Nicoli mariusn01 Data 14 martie 2021 12:38:20
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;
int a[302][302], S[302][302];
int n, m, i, j, i1, j1, i2, j2, x, suma, maxim, p;
int main() {
    ifstream fin ("teren.in");
    ofstream fout("teren.out");

    fin>>n>>m>>x;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++) {
            fin>>a[i][j];
            S[i][j] = S[i-1][j] + a[i][j];
        }
///    S[i][j] = suma de pe coloana j de sus pana in punctul (i,j)
        /**
3 5 1
0 0 1 0 1
0 1 1 0 0
0 0 0 1 0

0 0 1 0 1
0 1 2 0 1
0 1 2 1 1

        **/

    for (i1=1;i1<=n;i1++)
        for (i2=i1;i2<=n;i2++) {
            /// cu forurile de mai sus mi-am fixat in toate modurile posibile
            /// doua linii si ma va interesa ce se intampla intre ele
            suma = 0;
            p = 1;
            for (j=1;j<=m;j++) {
                suma += (S[i2][j] - S[i1-1][j]);
                while (suma > x) {
                    suma -= (S[i2][p] - S[i1-1][p]);
                    p++;
                }
                if ((j-p+1)*(i2-i1+1) > maxim)
                    maxim = (j-p+1)*(i2-i1+1);
            }
        }


    fout<<maxim;
}