Cod sursa(job #2412652)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 22 aprilie 2019 14:14:41
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <algorithm>
#include <stack>

const int NMAX=1005;

using namespace std;

ifstream cin ("dreptpal.in");
ofstream cout ("dreptpal.out");

int v[NMAX],z[NMAX],pal[NMAX][NMAX];
int n,m;

void palindrom(int lin)
{
    int r=0,c=0;
    for(int j=1; j<=m; ++j){
        if(j>r){
            while(j-z[j]>0 && j+z[j]<=m && v[j+z[j]]==v[j-z[j]])
                ++z[j];
        }
        else{
            int leftover=min(z[2*c-j],r-j);
            z[j]=leftover;
            while(j-z[j]>0 && j+z[j]<=m && v[j+z[j]]==v[j-z[j]])
                ++z[j];
        }
        if(j+z[j]>r){
            r=j+z[j];
            c=j;
        }
        pal[lin][j]=z[j]*2-1;
    }
    for(int j=1; j<=m; ++j)
        z[j]=0;
}

int rectangle(int col)
{
    // lucrez cu pal[1][col] ... pal[n][col]
    stack <int> st;
    int l[NMAX],r[NMAX];
    for(int i=1; i<=n; ++i){
        while(!st.empty() && pal[st.top()][col]>=pal[i][col])
            st.pop();
        if(st.empty())
            l[i]=0;
        else
            l[i]=st.top();
        st.push(i);
    }
    while(!st.empty())
        st.pop();
    for(int i=n; i>=1; --i){
        while(!st.empty() && pal[st.top()][col]>=pal[i][col])
            st.pop();
        if(st.empty())
            r[i]=n+1;
        else
            r[i]=st.top();
        st.push(i);
    }
    int maxim=(r[1]-l[1]-1)*pal[1][col];
    for(int i=2; i<=n; ++i)
        maxim=max(maxim,(r[i]-l[i]-1)*pal[i][col]);
    return maxim;
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j)
            cin>>v[j];
        palindrom(i);
    }
    int sol=0;
    for(int j=1; j<=m; ++j)
        sol=max(sol,rectangle(j));
    cout<<sol<<'\n';
    return 0;
}