Cod sursa(job #3264753)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 23 decembrie 2024 18:29:06
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <deque>
using namespace std;

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

#define int long long

int n,m;
int v[1001][1001];
int p[1001][1001];
int st1[1001],dr1[1001];
deque<int> q;

signed main()
{
    int i,j,st,dr,max1=0;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>v[i][j];
        }
    }
    for(i=1;i<=n;i++){
        st=1;dr=1;
        for(j=1;j<=m;j++){
            p[i][j]=max(0ll,min(dr-j,p[i][st+(dr-j)]));
            while(j+p[i][j]<=m && j-p[i][j]>0 && v[i][j-p[i][j]]==v[i][j+p[i][j]]){
                p[i][j]++;
            }
            if(j+p[i][j]>dr){
                st=j-p[i][j];dr=j+p[i][j];
            }
        }
    }
    for(j=1;j<=m;j++){
        q.clear();
        for(i=1;i<=n;i++){
            while(!q.empty() && p[q.back()][j]>=p[i][j]) q.pop_back();
            if(q.empty()) st1[i]=0;
            else st1[i]=q.back();
            q.push_back(i);
        }
        q.clear();
        for(i=n;i>=1;i--){
            while(!q.empty() && p[q.back()][j]>=p[i][j]) q.pop_back();
            if(q.empty()) dr1[i]=n+1;
            else dr1[i]=q.back();
            q.push_back(i);
        }
        for(i=1;i<=n;i++){
            ///printf("%d %d: %d %d %d\n",i,j,p[i][j]-1,dr1[i]-1,st1[i]+1);
            max1=max(max1,(2*(p[i][j]-1)+1)*((dr1[i]-1)-(st1[i]+1)+1));
        }
    }
    cout<<max1;
    return 0;
}