Cod sursa(job #1636467)

Utilizator stefanst77Luca Stefan Ioan stefanst77 Data 7 martie 2016 10:13:45
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("teren.in");
ofstream fout ("teren.out");

int b[305][305], v[305], n, m, x, amax;

void Formare()
{
    int i, j, y;
    fin >> n >> m >> x;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            fin >> y;
            b[i][j]=b[i-1][j]+y;
        }
    fin.close();
}
void Rezolva()
{
    int i, j, l1, l2, s, lgmax;
    amax=0;
    for (l1=1; l1<=n; l1++)
        for (l2=l1; l2<=n; l2++)
        {
            for (i=1; i<=m; i++) v[i]=b[l2][i]-b[l1-1][i];
            lgmax=s=0;
            i=1;
            for (j=1; j<=m; j++)
            {
                s+=v[j];
                while (s>x)
                {
                    s-=v[i];
                    i++;
                }
                lgmax=max(lgmax, j-i+1);
            }
            amax=max(amax, lgmax*(l2-l1+1));
        }
}
int main()
{
    Formare();
    Rezolva();
    fout << amax << "\n";
    return 0;
}