Cod sursa(job #2354323)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 25 februarie 2019 10:32:04
Problema DreptPal Scor 100
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;
int A[Nmax][Nmax], H[Nmax][Nmax];
int S[Nmax];

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            fin >> A[i][j];
    for(int i = 1; i <= N; i++)
    {
        int le = 1, ri = 1, len = 0;
        H[i][1] = 0;
        for(int j = 2; j <= M; j++)
        {
            if(j > ri)
                len = 0;
            else
                len = min(ri - j, H[i][le + ri - j]);
            while(j + len <= M && j - len >= 1 && A[i][j + len] == A[i][j - len])
                len++;
            len--;
            H[i][j] = len;
            if(j + len > ri)
            {
                ri = j + len;
                le = j - len;
            }
        }
    }
    int ans = 0;
    for(int j = 1; j <= M; j++)
    {
        int L = 0;
        for(int i = 1; i <= N; i++)
        {
            H[i][j] = 2 * H[i][j] + 1;
            while(L && H[i][j] <= H[S[L]][j])
            {
                ans = max(ans, H[S[L]][j] * (i - S[L - 1] - 1));
                L--;
            }
            S[++L] = i;
        }
        while(L)
        {
            ans = max(ans, H[S[L]][j] * (N - S[L - 1]));
            L--;
        }
    }
    fout << ans << "\n";
    return 0;
}