Cod sursa(job #3226819)

Utilizator Darius1414Dobre Darius Adrian Darius1414 Data 22 aprilie 2024 20:58:43
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <deque>
#define nmx 1005
using namespace std;
int v[nmx][nmx],s[nmx],n,m;
int main()
{
    ifstream f ("dreptpal.in");
    ofstream g ("dreptpal.out");
    f>>n>>m;
    for (int i=1; i<=n; i++)
    {
        s[0]=-1;
        for (int j=1; j<=m; j++)
            f>>s[j];
        s[m+1]=-2;
        int center=0,right=0,mirror;
        for (int j=1; j<=m+1; j++)
        {
            mirror=2*center-j;
            if (j<right)
                v[i][j]=min(v[i][mirror],right-j);
            while (s[j+1+v[i][j]]==s[j-(1+v[i][j])])
                v[i][j]++;
            if (j+v[i][j]>right)
            {
                center=j;
                right=j+v[i][j];
            }
        }
        for (int j=1; j<=m; j++)
            v[i][j]=v[i][j]*2+1;
    }
    deque <int> dq;
    int st[nmx],dr[nmx],mx=0;
    for (int j=1; j<=m; j++)
    {
        dq.clear();
        for (int i=1; i<=n; i++)
        {
            while (!dq.empty() && v[dq.front()][j]>=v[i][j])
                dq.pop_front();
            if (dq.empty())
                st[i]=0;
            else st[i]=dq.front();
            dq.push_front(i);
        }
        dq.clear();
        for (int i=n; i>=1; i--)
        {
            while (!dq.empty() && v[dq.front()][j]>=v[i][j])
                dq.pop_front();
            if (dq.empty())
                dr[i]=n+1;
            else dr[i]=dq.front();
            mx=max(mx,v[i][j]*(dr[i]-st[i]-1));
            dq.push_front(i);
        }
    }
    g<<mx;
}