Cod sursa(job #1520684)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 9 noiembrie 2015 11:00:56
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

int n,m,a,i,j,ii,jj,u,x,i1,i2,nr,p,maxim,s[305][305];

//long long s,ok;

ifstream fin ("teren.in");

ofstream fout ("teren.out");

int main (){

    fin>>n>>m>>x;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            fin>>a;
            if (a == 1)
                nr++;
            s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a;
            //fout<<s[i][j]<<" ";
        }
        //fout<<"\n";
    }
    for (i1=1;i1<=n;i1++)
        for (i2=i1;i2<=n;i2++) {
            p = 1;
            for (u=1;u<=m;u++) {
                while (s[i2][u]-s[i2][p-1]-s[i1-1][u] + s[i1-1][p-1] > x && p<=u)
                    p++;
                if ((u-p+1) * (i2-i1+1) > maxim)
                    maxim = (u-p+1) * (i2-i1+1);

            }
        }

    fout<<maxim;
   /* maxim = 0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            for (ii=i;ii<=n;ii++)
                for (jj=j;jj<=m;jj++){
                    nr = s[ii][jj]-s[i-1][jj]-s[ii][j-1]+s[i-1][j-1];
                    if (nr <= p && (ii-i+1)*(jj-j+1) > maxim)
                        maxim = (ii-i+1)*(jj-j+1);
                }


    fout<<maxim;


/*    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            for (ii=i;ii<=n;ii++){
                for (jj=j;jj<=m;jj++){
                    s = 0;
                    for (x=i;x<=ii;x++)
                        for (y=j;y<=jj;y++)
                            s+=a[x][y];
                    if ((ii-i+1)*(jj-j+1) > maxim && s<=p){
                        maxim = (ii-i+1)*(jj-j+1);
                       //ok = (ii-i+1)*(jj-j+1);
                    }
                }
            }

    fout<<maxim;
*/
    return 0;
}