Cod sursa(job #2324175)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 20 ianuarie 2019 12:53:26
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 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;
}