Cod sursa(job #1593706)

Utilizator CraiuAndrei Craiu Craiu Data 8 februarie 2016 20:11:42
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

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

void Solve()
{
    int i, j, suma, p, st, dr, mx;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + a[i][j];
    mx = 0;
    for(i = 1; i <= n; i++)
        for(j = i; j <= n; j++)
        {
            for(p = 1; p <= m; p++)
                v[p] = s[j][p] - s[i - 1][p];
            st = 1;
            suma = 0;
            for(dr = 1; dr <= m; dr++)
            {
                suma += v[dr];
                while(st <= dr && suma > k)
                {
                    suma -= v[st];
                    st++;
                }
                if(st <= dr) mx = max(mx, (j - i + 1)*(dr - st + 1));
            }
        }
    ofstream fout("teren.out");
    fout << mx << "\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}