Cod sursa(job #1681797)

Utilizator GinguIonutGinguIonut GinguIonut Data 9 aprilie 2016 18:42:17
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

#define nMax 1003
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m, Sol;
int mat[nMax][nMax], dp[nMax][nMax];
struct stiva
{
    int poz;
    int ind;
}Stck[nMax];
void read()
{
    fin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>mat[i][j];
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        int C=0, R=0;
        for(int j=1;j<=m;j++)
        {
            if(j<=R)
                dp[i][j]=min(dp[i][C-(j-C)], R-j+1);
            while(mat[i][j+dp[i][j]]==mat[i][j-dp[i][j]] && j+dp[i][j]<=m && j-dp[i][j]>=1)
                dp[i][j]++;
            if(j+dp[i][j]-1>R)
            {
                C=j;
                R=j+dp[i][j]-1;
            }
        }
    }

    for(int j=1;j<=m;j++)
    {
        int top=0;
        for(int i=1;i<=n+1;i++)
        {
            int pozi=i;
            while(dp[i][j]<dp[Stck[top].ind][j] && top>=1)
            {
                Sol=max(Sol, (dp[Stck[top].ind][j]*2-1)*(i-Stck[top].poz));
                pozi=Stck[top].poz;
                top--;
            }

            Stck[++top].ind=i;
            Stck[top].poz=pozi;

        }
    }
}
void write()
{
    fout<<Sol;
}
int main()
{
    read();
    solve();
    write();
    return 0;
}