Cod sursa(job #1534030)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 23 noiembrie 2015 10:46:57
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;
int s[302][302];
int main()
{
    FILE *fin=fopen ("teren.in","r");
    FILE *fout=fopen ("teren.out","w");
    int n,m,x,i,j,maxi,y,ii,jj;
    fscanf (fin,"%d%d%d",&n,&m,&x);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
             fscanf (fin,"%d",&y);
             s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+y;
        }
    // avem matricea cu sume partiale
    maxi=0;
    for (i=1;i<=n;i++)
        for (ii=i;ii<=n;ii++){
        // am fixat 2 linii
        j=1;
        // j e coloana care variaza!!!
        for (jj=1;jj<=m;jj++){
            while (s[ii][jj]-s[ii][j-1]-s[i-1][jj]+s[i-1][j-1]>x && j<=jj)
             j++;
             // cautam aria maxima a terenului care se termina pe coloana jj si liniile i si ii
            if ((ii-i+1)*(jj-j+1)>maxi)
                maxi=(ii-i+1)*(jj-j+1);
            // calculam maximul
        }
    }
    fprintf (fout,"%d",maxi);
    return 0;
}