Cod sursa(job #1727749)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 11 iulie 2016 15:52:36
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
int b[303][303],v[303],x,n,Amax,m;

void Citire()
{
    int i,j,w;
    ifstream fin ("teren.in");

    fin >> n >> m >> x;

    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            fin >> w;
            b[i][j]=b[i-1][j]+w;
        }
    fin.close();
}

void Rezolva()
{
    int i,j,lgmax,l1,s,l2;
    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=0;
            i=1;
            s=0;
            for(j=1; j<=m; j++)
            {
                s+=v[j];
                while(s>x)s-=v[i++];
                lgmax=max(lgmax,j-i+1);
            }

            Amax=max(Amax,lgmax*(l2-l1+1));
        }
}

int main()
{
    ofstream fout ("teren.out");
    Citire();
    Rezolva();
    fout << Amax << "\n";
    fout.close();
    return 0;
}