Cod sursa(job #1596917)

Utilizator tudi98Cozma Tudor tudi98 Data 11 februarie 2016 15:11:54
Problema DreptPal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <stack>
using namespace std;

int n,m;
int a[1001][1001];
int p[1001][1001];
stack<int> S;

void Manacher(int A[],int P[])
{
    int l = 0,r = -1;
    for (int i = 1; i <= m; i++) {
        if (i > r) P[i] = 1;
        else P[i] = min(P[l+r-i],r-i+1);
        int L = i - P[i] + 1;
        int R = P[i] + i - 1;
        while (L-1 >= 1 && R+1 <= m && A[L-1] == A[R+1]) L--,R++,P[i]++;
        if (R > r)
            r = R, l = L;
    }

    for (int i = 1; i <= m; i++)
        P[i] = P[i] * 2 - 1;
}

int Solve(int j)
{
    int Ret = n;
    for (int i = 1; i <= n; i++) {
        if (S.empty() || p[S.top()][j] <= p[i][j]) S.push(i);
        else {
            int u = S.top();
            while (!S.empty() && p[S.top()][j] > p[i][j]) {
                Ret = max(Ret,(u-S.top()+1)*p[S.top()][j]);
                S.pop();
            }
            S.push(i);
        }
    }
    int u = S.top();
    while (!S.empty()) {
        Ret = max(Ret,(u-S.top()+1)*p[S.top()][j]);
        S.pop();
    }
    return Ret;
}

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

    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++)
        Manacher(a[i],p[i]);

    int Ans = n;
    for (int j = 1; j <= m; j++)
        Ans = max (Ans, Solve(j));

    fout << Ans;
}