Cod sursa(job #3207060)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 24 februarie 2024 21:34:24
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <stack>
const int NMAX=1005;

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

void manacher(int [], int [], int);

int ans[NMAX][NMAX], a[NMAX][NMAX];
int p[NMAX], dr[NMAX], stt[NMAX];
int n, m;
stack <int> st;

int main()
{
    int i, j, maxim=0;
    fin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            fin>>a[i][j];
        }
        manacher(ans[i], a[i], m);
        for(j=1; j<=m; j++) fout<<ans[i][j]<<' ';
        fout<<'\n';
    }
    for(j=1; j<=m; j++)
    {
        for(i=1; i<=n; i++)
        {
            while(!st.empty() && ans[st.top()][j]>ans[i][j])
            {
                dr[st.top()]=i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty())
        {
            dr[st.top()]=n+1;
            st.pop();
        }
        for(i=n; i>=1; i--)
        {
            while(!st.empty() && ans[st.top()][j]>ans[i][j])
            {
                stt[st.top()]=i;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty())
        {
            stt[st.top()]=0;
            st.pop();
        }
        for(i=1; i<=n; i++)
        {
            //fout<<i<<' '<<j<<' '<<stt[i]<<' '<<dr[i]<<' '<<ans[i][j]<<'\n';
            maxim=max(maxim, (dr[i]-stt[i]-1)*(2*ans[i][j]-1));
        }
    }
    fout<<maxim<<'\n';
    return 0;
}

void manacher(int ans[], int v[], int lg)
{
    int i;
    int dr=0, st=0;
    for(i=1; i<=lg; i++)
    {
        if(dr<i) ans[i]=1;
        else ans[i]=min(ans[dr+st-i], dr-i+1);
        while(true)
        {
            if(i-ans[i]<0 || i+ans[i]>lg) break;
            if(v[i-ans[i]]==v[i+ans[i]]) ans[i]++;
            else break;
        }
        ans[i]--;
        if(dr<=ans[i])
        {
            dr=i+ans[i];
            st=i-ans[i];
        }
    }
    for(i=1; i<=lg; i++) ans[i]++;
}