Cod sursa(job #1513935)

Utilizator akaprosAna Kapros akapros Data 30 octombrie 2015 11:59:08
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1005
using namespace std;
int n, m, i, j, l, pos, ap, len[maxN], s;
int a[maxN], top[maxN];
long A, maxA;
struct stack
{
    int h;
    int w;
}st[maxN][maxN];
void rs()
{
    freopen("dreptpal.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n + 1; ++ i)
    {
        for (j = 1; j <= m; ++ j)
            scanf("%d", &a[j]);
        pos = 1;
        ap = 1;
        for (j = 1; j <= m + 1; ++ j)
        {
            len[j] = 0;
             if (j <= pos)
                    len[j] = min(len[2 * ap - j], pos - j);
             while (j - len[j] - 1 > 0 && j + len[j] + 1 <= m &&
                   a[j - len[j] - 1] == a[j + len[j] + 1])
                    ++ len[j];
             if (j + len[j] > pos)
             {
                 pos = j + len[j];
                 ap = j;
             }
             s = 0;
             l = len[j] * 2 + 1;
             if (j == m + 1 || i == n + 1)
                l = 0;
             while (top[j] && st[j][top[j]].w > l)
             {
                 s += st[j][top[j]].h;
                 A = st[j][top[j]].w * s;
                 -- top[j];
                 if (A > maxA)
                    maxA = A;
             }
             if (st[j][top[j]].w == l)
                st[j][top[j]].h += s + 1;
            else
            {
                st[j][++ top[j]].w = l;
                st[j][top[j]].h = s + 1;
            }
        }
    }
}
void write()
{
    freopen("dreptpal.out", "w", stdout);
    printf("%ld", maxA);
}
int main()
{
    rs();
    write();
    return 0;
}