Cod sursa(job #2698578)

Utilizator dimi999Dimitriu Andrei dimi999 Data 22 ianuarie 2021 15:39:54
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <stack>
using namespace std;

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

int a[1005][1005];
short int Pal[2005][2005], N, M;

void Manacher()
{
    int v[2005];

    for(int line  = 1; line <= N; line++)
    {
        v[0] = -1;
        for(int i = 1; i <= N; i++)
            v[2 * i - 1] = a[line][i];

        v[2 * N + 1] = -2;

        for(int i = 2; i <= 2 * N; i += 2)
            v[i] = -3;

        int C = 0, R = 0;

        for(int i = 1; i <= 2 * N; i++)
        {
            int mirror = 2 * C - i;

            if(i < R)
                Pal[line][i] = min(Pal[line][mirror], (short int)(R - i));

            while(v[i + Pal[line][i] + 1] == v[i - Pal[line][i] - 1])
                Pal[line][i]++;

            if(i + Pal[line][i] > R)
            {
                C = i;
                R = i + Pal[line][i];
            }
        }
    }
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            fin >> a[i][j];

    Manacher();

    stack <int> st;

    int sol = 0;

    for(int j = 1; j <= 2 * M; j++)
    {

        for(int i = 1; i <= N; i++)
            if(st.empty() || Pal[st.top()][j] <= Pal[i][j])
                st.push(i);
            else
                {
                    int pas = 1;

                    sol = max(sol, (int)Pal[st.top()][j]);
                    st.pop();

                    while(!st.empty() && Pal[st.top()][j] > Pal[i][j])
                    {
                        pas++;
                        sol = max(sol, (int)Pal[st.top()][j] * pas);
                        st.pop();
                    }

                    st.push(i);
                }

        int pas = 1;

        sol = max(sol, (int)Pal[st.top()][j]);
        st.pop();

        while(!st.empty())
            {
                pas++;
                sol = max(sol, (int)Pal[st.top()][j] * pas);
                st.pop();
            }

    }

    fout << sol << '\n';

    return 0;
}