Cod sursa(job #3209703)

Utilizator alex_0747Gheorghica Alexandru alex_0747 Data 3 martie 2024 12:47:10
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <stack>
#define N 1005
using namespace std;

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

int a[N][N], lps[N][N], l[N], r[N], v[N], n, m, mx;

void Manacher(int a[], int lps[])
{
    int i, st, dr;
    st = dr = 1;
    a[0] = -2e9; a[m + 1] = 2e9;
    for (i = 1; i <= m; i++)
    {
        lps[i] = max(0, min(dr - i, lps[st + (dr - i)]));
        while (a[i - lps[i]] == a[i + lps[i]])
            lps[i]++;
        if (i + lps[i] > dr)
        {
            st = i - lps[i];
            dr = i + lps[i];
        }
    }
}

void SmecherieCuStDr()
{
    stack <int> st;
    int i;
    v[0] = v[n + 1] = -1;
    for (i = 1; i <= n; i++)
        v[i] = 2 * v[i] - 1;
    st.push(0);
    for (i = 1; i <= n; i++)
    {
        while (v[i] <= v[st.top()])
            st.pop();
        l[i] = st.top();
        st.push(i);
    }
    while (!st.empty())
        st.pop();
    st.push(n + 1);
    for (i = n; i >= 1; i--)
    {
        while (v[i] <= v[st.top()])
            st.pop();
        r[i] = st.top();
        st.push(i);
    } 
    for (i = 1; i <= n; i++)
        mx = max(mx, v[i] * (r[i] - l[i] - 1));
}

int main()
{
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            fin >> a[i][j];
    for (i = 1; i <= n; i++)
        Manacher(a[i], lps[i]);
    for (j = 1; j <= m; j++)
    {
        for (i = 1; i <= n; i++)
            v[i] = lps[i][j];
        SmecherieCuStDr();
    }
    fout << mx << "\n";
    fout.close();
    return 0;
}