Cod sursa(job #2347776)

Utilizator pishcotMiruna Turbatu pishcot Data 19 februarie 2019 08:46:52
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("teren.in");
ofstream fout("teren.out");
int n, m, a[305][305];
int sum_col[305][305];
int t[305];
int x;
int main()
{
    int A = 0;
    fin >> n >> m >> x;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            fin >> a[i][j];
            sum_col[i][j] = a[i][j] + sum_col[i - 1][j];
        }

    for(int l1 = 1; l1 <= n; l1++)
        for(int l2 = l1; l2 <= n; l2++)
        {
            int H = l2 - l1 + 1;
            for(int j = 1; j <= m; j++)
                t[j] = sum_col[l2][j] - sum_col[l1 - 1][j];
            int suma  = 0;
            int j = 1;
            for(int 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";
    return 0;
}

/**
3 5 1
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0

9
*/