Cod sursa(job #2174935)

Utilizator BogdanFaciuIntaiulMare Lake BogdanFaciuIntaiul Data 16 martie 2018 14:19:10
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("teren.in");
ofstream g("teren.out");

int n,m,x,s[302][302],S,Max;

int main()
{
    f>>n>>m>>x;
    int i,j,i1,i2,j1,j2;
    ///matricea sumelor partiale pe linii
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            f>>s[i][j];
            s[i][j]+=s[i-1][j];
        }
    ///cautam dreptunghiurile cuprinse intre doua linii i si k
    for(i1=1;i1<=n;i1++)
        for(i2=i1;i2<=n;i2++)
        {
            j1=1; j2=1; //dreptunghiul cuprins intre coloanele j1 si j2
            S=s[i2][1]-s[i1-1][1];
            while(j2<=m)
            {
                while(S<=x && j2<=m)
                {
                    j2++;
                    S+=s[i2][j2]-s[i1-1][j2];
                }

                if(S-(s[i2][j2]-s[i1-1][j2])<=x)
                    Max=max((i2-i1+1)*(j2-j1),Max);
                while(S>x && j1<=j2)
                {
                    S-=(s[i2][j1]-s[i1-1][j1]);
                    j1++;
                }
            }
        }
    g<<Max;
    return 0;
}