Cod sursa(job #2356807)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 26 februarie 2019 21:54:14
Problema DreptPal Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
#define NMAX 1005

using namespace std;

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

int N, M, v[NMAX][NMAX], D[NMAX][NMAX], L, R, len;
int stv[NMAX], k, MX, arie;

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            fin >> v[i][j];
    for (int i = 1; i <= N; i++)
    {
        L = R = 0;
        for (int j = 1; j <= M; j++)
        {
            if (j > R)
                len = 0;
            else
                len = min(R - j, D[i][L + R - j]);
            while (j - len > 0 && j + len <= M && v[i][j - len] == v[i][j + len])
                len++;
            len--;
            D[i][j] = len;
            if (j + len > R)
            {
                R = j + len;
                L = j - len;
            }
        }
    }
    for (int j = 1; j <= M; j++)
    {
        k = 0;
        for (int i = 1; i <= N; i++)
        {
            while (D[stv[k]][j] >= D[i][j] && k)
            {
                arie = (2 * D[stv[k]][j] + 1) * (i - 1 - stv[k - 1]);
                MX = max(MX, arie);
                k--;
            }
            stv[++k] = i;
        }
        while (k)
        {
            arie = (2 * D[stv[k]][j] + 1) * (N - 1 - stv[k - 1]);
            MX = max(MX, arie);
            k--;
        }
    }
    fout << MX;
    return 0;
}