Cod sursa(job #1591229)

Utilizator dnprxDan Pracsiu dnprx Data 5 februarie 2016 21:57:20
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

char a[302][302];
int b[302][302], n, m, X, t[302];

void Citire()
{
    char s[1000];
    int i, j;
    ifstream fin("teren.in");
    fin >> n >> m >> X;
    fin.get();
    for (i = 1; i <= n; ++i)
    {
        fin.getline(s + 1, 998);
        for (j = 1; j <= m; ++j)
            a[i][j] = s[2 * j - 1];
    }
}

void SumePeColoana()
{
    int i, j;
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            if (a[i][j] == '0') b[i][j] = b[i-1][j];
            else b[i][j] = 1 + b[i-1][j];
}

void Rezolva()
{
    int L1, L2, i, j, H, Aria, nr1;
    Aria = 0;
    for (L1 = 1; L1 <= n; ++L1)
        for (L2 = L1; L2 <= n; ++L2)
        {
            H = L2 - L1 + 1;
            for (i = 1; i <= m; ++i)
                t[i] = b[L2][i] - b[L1 - 1][i];
            j = 1; nr1 = 0;
            for (i = 1; i <= m; ++i)
            {
                nr1 += t[i];
                while (nr1 > X)
                {
                    nr1 -= t[j];
                    j++;
                }
                Aria = max(Aria, H * (i - j + 1));
            }
        }
    ofstream fout("teren.out");
    fout << Aria << "\n";
    fout.close();
}

int main()
{
    Citire();
    SumePeColoana();
    Rezolva();
    return 0;
}