Cod sursa(job #2347765)

Utilizator NopeCarp Rafael Nope Data 19 februarie 2019 08:39:49
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("teren.in");
ofstream fout("teren.out");

int a[305][305] , n , m , x;
int s[305][305], t[305];

int main()
{
    int i , j, l1 , l2, suma, A = 0, H;
    fin >> n >> m >> x;
    for (i = 1 ; i <= n ; i++)
        for (j = 1 ; j <= m ; j++)
        {
            fin >> a[i][j];
            s[i][j] = s[i-1][j] + a[i][j];
        }

    for (l1 = 1; l1 <= n ; l1++)
        for (l2 = l1 ; l2 <= n ; l2++)
        {
            H = l2 - l1 + 1;
            for (i = 1 ; i <= m ; i++)
                t[i] = s[l2][i] - s[l1 - 1][i];
            /// aflu cea mai lunga secv. care contine
            /// cel mult x de 1
            j = 1;
            suma = 0;
            for (i=1; i <= m; i++)
            {
                suma += t[i];
                while (suma > x)
                {
                    suma -= t[j];
                    j++;
                }
                A = max(A, (i - j + 1) * H);
            }
        }
    fout << A << "\n";
    fout.close();
    return 0;
}
/** x=3
0 0 0 0 1
0 1 0 0 0 l1
1 1 0 1 0
1 0 1 0 1 l2 t = 2, 2, 1, 1, 1
1 1 1 1 0
*/