Cod sursa(job #2595858)

Utilizator alexradu04Radu Alexandru alexradu04 Data 8 aprilie 2020 16:05:13
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 305;
int sp[NMAX][NMAX],a[NMAX];
int m , n , k;

int main()
{
    freopen("teren.in","r",stdin);
    freopen("teren.out","w",stdout);
    scanf("%d%d%d",&m,&n,&k);
    int x;
    for(int i = 1 ; i <= m ; i++)
        for(int j = 1 ; j <= n ; j++)
        {
            scanf("%d",&x);
            sp[i][j] = sp[i-1][j]+x;
        }
    int sum = 0 , ma = 0 ;
    for(int l1 = 1 ; l1 <= m ; l1++)
    {
        for(int l2 = l1 ; l2 <= m ; l2++)
        {
            int dif = l2-l1+1;
            for(int j = 1 ; j <= n ; j++)
                a[j] = sp[l2][j] - sp[l1-1][j];
            int st,dr;
            sum = 0;
            st = 1;
            for(dr = 1 ; dr <= n ; dr++)
            {
                sum += a[dr];
                while(st <= dr && sum > k)
                {
                    sum -= a[st];
                    st++;
                }
                if(st <= dr)
                    ma = max(ma,dif*(dr-st+1));
            }
        }
    }
    printf("%d",ma);
    return 0;
}