Cod sursa(job #2478406)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 21 octombrie 2019 23:55:30
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int NMAX = 1005;
const int INF = 2e9;
int m , n;
int a[NMAX][NMAX], v[NMAX], b[NMAX][NMAX] , st[NMAX] , dr[NMAX], ans;
vector<int>s;
stack<int>stiva;

void emptyStack()
{
    while(!stiva.empty()) stiva.pop();
}

int main()
{
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    scanf("%d%d",&m,&n);
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
            scanf("%d",&a[i][j]);
        memset(v,0,sizeof(v));
        s.clear();
        s.push_back(INF+1);
        for(int j = 1 ; j <= n ; j++)
        {
            s.push_back(INF+666013);
            s.push_back(a[i][j]);
        }
        s.push_back(INF+666013);
        s.push_back(INF+13);

        int C,R;
        C = R = 0;
        for(int j = 1 ; j < s.size() - 1 ; j++)
        {
            v[j] = 0;
            int mirror = 2*C-j;
            if(j < R)
                v[j] = min(R-j,v[mirror]);
            while(s[j+v[j]+1] == s[j-v[j]-1]) v[j]++;
            if(j+v[j] > R)
            {
                C = j;
                R = j+v[j];
            }
        }
        for(int j = 2 ; j <= 2*n ; j+=2)
            b[i][j/2] = v[j]/2*2+1;
    }

    for(int j = 1 ; j <= n ; j++)
    {
        memset(dr,0,sizeof(dr));
        memset(st,0,sizeof(st));
        emptyStack();
        stiva.push(1);
        for(int i = 2 ; i <= m ; i++)
        {
            while(!stiva.empty() && b[i][j] <= b[stiva.top()][j])
                stiva.pop();
            if(!stiva.empty())
                st[i] = stiva.top();
            else
                st[i] = 0;
            stiva.push(i);
        }

        emptyStack();
        stiva.push(m);
        dr[m] = m+1;
        for(int i = m-1 ; i >= 1 ; i--)
        {
            while(!stiva.empty() && b[i][j] <= b[stiva.top()][j])
                stiva.pop();
            if(!stiva.empty())
                dr[i] = stiva.top();
            else
                dr[i] = m+1;
            stiva.push(i);
        }

        for(int i = 1 ; i <= m ; i++)
            ans = max(ans,b[i][j]*(dr[i]-st[i]-1));
    }
    printf("%d\n",ans);
    return 0;
}