Cod sursa(job #2698615)

Utilizator dimi999Dimitriu Andrei dimi999 Data 22 ianuarie 2021 16:27:47
Problema DreptPal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <stack>
using namespace std;

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

int a[1010][1010], N, M;
int Pal[1010][2010];

void Manacher()
{
    int v[2010];

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

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

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

        int C = 0, R = 0;

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

            if(i < R)
                Pal[line][i] = min(Pal[line][mirror], (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 + 1; j++)
    {

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

                    while(!st.empty() && Pal[st.top()][j] > Pal[i][j])
                    {
                        int val = Pal[st.top()][j];
                        st.pop();

                        if(st.empty())
                            border = 0;
                        else
                            border = st.top();

                        sol = max(sol, (i - 1 - border) * val);
                    }

                    st.push(i);
                }

       int border;

        while(!st.empty())
            {
                int val = Pal[st.top()][j];
                st.pop();

                if(st.empty())
                    border = 0;
                else
                    border = st.top();

                sol = max(sol, (N - border) * val);
            }
    }

    fout << sol << '\n';

    return 0;
}