Cod sursa(job #1624532)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 2 martie 2016 11:50:10
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

int n,m,k;
bool a[305][305];
int t[305][305] , v[305] ;

void Citire()
{
    int i,j;
    ifstream f("teren.in");
    f >> n >> m >> k;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            f >> a[i][j];
    f.close();
}

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));
            }
        }
    ofstream g("teren.out");
    g << maxim << "\n";
}

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