Cod sursa(job #1623960)

Utilizator antanaAntonia Boca antana Data 1 martie 2016 23:02:51
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#define MAX 300
using namespace std;
int v[MAX+1][MAX+1], s[MAX+1][MAX+1];
inline int maxim(int a, int b){
    if(a>b)
        return a;
    return b;
}
int main()
{
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);
    int n, m, i, i1, i2, j, st, dr, sum, k, amax=0;
    scanf("%d%d%d", &n, &m, &k);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d", &v[i][j]);
    for(j=1;j<=m;j++)
        for(i=1;i<=n;i++)
            s[i][j]=v[i][j]+s[i-1][j];
    for(i1=1;i1<=n;i1++)
        for(i2=i1;i2<=n;i2++)
        {
            sum=s[i2][1]-s[i1-1][1];
            st=dr=1;
            while(st<=m)
            {
                while(dr<m&&sum+s[i2][dr+1]-s[i1-1][dr+1]<=k)
                {
                    dr++;
                    sum+=s[i2][dr]-s[i1-1][dr];
                }
                if(sum<=k)
                    amax=maxim(amax, (i2-i1+1)*(dr-st+1));
                sum-=s[i2][st]-s[i1-1][st];
                st++;
            }
        }
    printf("%d", amax);
    return 0;
}