Cod sursa(job #2350897)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 21 februarie 2019 19:45:27
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("teren.in");
ofstream fout("teren.out");
int a[400][400],n,k,i,j,i1,i2,st,dr,m,sol;
bool verif(int x1,int y1,int x2,int y2){
int sum=0;
sum+=a[x1-1][y1-1];
sum-=a[x1-1][y2]+a[x2][y1-1];
sum+=a[x2][y2];

return (sum<=k);
}
int main(){
    fin>>n>>m>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        fin>>a[i][j];
        a[i][j]+=(a[i-1][j]+a[i][j-1]-a[i-1][j-1]);
        /// in tot patratul a[i-1][j-1] cele 2 matrici se suprapun deci apare de 2 ori in suma
    }

for(i1=1;i1<=n;i1++)
for(i2=1;i2<=i1;i2++){
    st=1;
    for(dr=1;dr<=m;dr++){
        while(verif(i2,st,i1,dr)==0)
            st++;
        sol=max(sol, (i1-i2+1)*(dr-st+1) );
    }
}
fout<<sol;
}