Cod sursa(job #1608601)

Utilizator CarabasRobertCarabas Robert-Iancu CarabasRobert Data 22 februarie 2016 10:56:38
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("teren.in");
ofstream fout ("teren.out");
int n,m,k;
bool a[305][305];
int t[305][305] , v[305] ;
void Citire()
{
    int i,j;
    fin >> n >> m >> k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin >> a[i][j];
}

void Rezolvare()
{
    int i,j,s,p,st,dr, maxim;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            t[i][j]=t[i-1][j]+a[i][j];
    maxim=0;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
        {
            for(p=1;p<=m;p++)
                v[p]=t[j][p]-t[i - 1][p];
            st=1;
            s=0;
            for(dr=1;dr<=m;dr++)
            {
                s+=v[dr];
                while(st<=dr&&s>k)
                {
                    s-=v[st];
                    st++;
                }
                if(st<=dr) maxim=max(maxim,(j-i+1)*(dr-st+1));
            }
        }
    fout << maxim << "\n";
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}