Cod sursa(job #2555420)

Utilizator trifangrobertRobert Trifan trifangrobert Data 24 februarie 2020 00:20:06
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1005;
int N, M;
int a[NMAX][NMAX], palin[NMAX][NMAX];

void Manacher(int line)
{
    int left, right, k;
    left = 0, right = 0;
    for (int i = 1;i <= M;++i)
    {
        if (i > right)
        {
            k = 1;
            while (i - k >= 1 && i + k <= M && a[line][i - k] == a[line][i + k])
                ++k;
            palin[line][i] = k;
        }
        else
        {
            k = palin[line][left + right - i];
            if (i + k - 1 < right)
                palin[line][i] = k;
            else
            {
                k = right - i;
                while (i - k >= 1 && i + k <= M && a[line][i - k] == a[line][i + k])
                    ++k;
                palin[line][i] = k;
            }
        }
    }
}

int st[NMAX], top, stg[NMAX], drp[NMAX], v[NMAX], answer;

void Solve(int col)
{
    for (int i = 1;i <= N;++i)
        v[i] = palin[i][col];
    top = 0;
    v[0] = -1;
    st[top] = 0;
    for (int i = 1;i <= N;++i)
    {
        while (top > 0 && v[i] <= v[st[top]])
            --top;
        stg[i] = i - st[top];
        st[++top] = i;
    }
    top = 0;
    v[N + 1] = -1;
    st[top] = N + 1;
    for (int i = N;i >= 1;--i)
    {
        while (top > 0 && v[i] <= v[st[top]])
            --top;
        drp[i] = st[top] - i;
        st[++top] = i;
    }

    for (int i = 1;i <= N;++i)
        answer = max(answer, (2 * v[i] - 1) * (stg[i] + drp[i] - 1));
}

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(i);
    for (int j = 1;j <= M;++j)
        Solve(j);
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}