Cod sursa(job #2859620)

Utilizator mateitudordmDumitru Matei mateitudordm Data 1 martie 2022 17:33:04
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#define nmax 300
#pragma GCC optimize("Ofast")

using namespace std;

int mat[nmax + 1][nmax + 1];

int main()
{
    ifstream cin("teren.in");
    ofstream cout("teren.out");
    int n, m, k, i, j, l, c, st, dr, mij, sol, maxx = 0, act;
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (n > m)
                cin >> mat[i][j], mat[i][j] = mat[i][j] + mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
            else
                cin >> mat[j][i], mat[j][i] = mat[j][i] + mat[j - 1][i] + mat[j][i - 1] - mat[j - 1][i - 1];
    if (n < m)
        swap(n, m);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            sol = n;
            for (c = j; c <= m && mat[i][c] - mat[i - 1][c] - (mat[i][j - 1] - mat[i - 1][j - 1]) <= k; c++)
            {
                while (mat[sol][c] - mat[i - 1][c] - mat[sol][j - 1] + mat[i - 1][j - 1] > k)
                    sol--;
                if ((sol - i + 1) * (c - j + 1) > maxx)
                    maxx = (sol - i + 1) * (c - j + 1);
            }
        }
    cout << maxx;
    return 0;
}