Cod sursa(job #1516898)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 3 noiembrie 2015 18:22:50
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013

using namespace std;

int n, m, i, j, rgt, pal, mx;
int st[1005], dr[1005];
int a[1005][1005], l[1005][1005];

stack <int> stv;

int main()
{
    freopen("dreptpal.in", "r", stdin);
    freopen("dreptpal.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    for(i = 1; i <= n; i++)
    {
        rgt = pal = 0;
        for(j = 1; j <= m; j++)
        {
            if(rgt >= j)
            {
                if(l[i][2 * pal - j] < rgt - j + 1)
                {
                    l[i][j] = l[i][2 * pal - j];
                    continue;
                }
                else
                    l[i][j] = rgt - j + 1;
            }
            else
                l[i][j] = 1;

            while(a[i][ j + l[i][j] ] == a[i][ j - l[i][j] ] && j + l[i][j] <= m && j - l[i][j] >= 1)
                l[i][j]++;

            if(j + l[i][j] - 1 > rgt)
            {
                rgt = j + l[i][j] - 1;
                pal = j;
            }
        }
    }

    for(j = 1; j <= m; j++)
    {
        while(!stv.empty())
            stv.pop();

        for(i = 1; i <= n; i++)
        {
            while(!stv.empty() && l[stv.top()][j] >= l[i][j])
                stv.pop();

            if(stv.empty())
                st[i] = 1;
            else
                st[i] = stv.top() + 1;

            stv.push(i);
        }

        while(!stv.empty())
            stv.pop();

        for(i = n; i >= 1; i--)
        {
            while(!stv.empty() && l[stv.top()][j] >= l[i][j])
                stv.pop();

            if(stv.empty())
                dr[i] = n;
            else
                dr[i] = stv.top() - 1;

            stv.push(i);
        }

        for(i = 1; i <= n; i++)
            mx = max(mx, (l[i][j] * 2 - 1) * (dr[i] - st[i] + 1));
    }

    printf("%d", mx);

    return 0;
}