Cod sursa(job #872439)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 6 februarie 2013 01:37:30
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
FILE *f=fopen("teren.in","r"), *g=fopen("teren.out","w");

long int n, m, x, max=0, a[305][305], k[303];

void citire(){
long int i, j;
    fscanf(f,"%ld %ld %ld\n",&n,&m,&x);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            fscanf(f,"%ld",&a[i][j]);
            a[i][j]+=a[i-1][j];
        }
    }
}

void rezolv(){
long int i1, i2, j, dr, st, sum, posmax;

    for(i1=1;i1<=n;i1++){

        for(i2=i1;i2<=n;i2++){

            for(j=1;j<=m;j++){
                k[j]= a[i2][j]-a[i1-1][j];
            }

            st=1; dr=0; sum=0;

            while(dr<m){
                dr++; sum+=k[dr];

                if(sum<=x){
                    posmax= (i2-i1+1)*(dr-st+1);if(max<posmax){max=posmax;}
                }
                else{
                    while(sum>x){sum-=k[st]; st++;} // Aici nu mai verif daca e buna aria ptr ca nu are cum sa fie mai mare decat max
                }
            }

        }

    }

    fprintf(g,"%ld\n",max);


}

int main(){

    citire();
    rezolv();

return 0;
}