Cod sursa(job #1100768)

Utilizator Ionut228Ionut Calofir Ionut228 Data 7 februarie 2014 14:20:59
Problema DreptPal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <algorithm>
#include <stack>

using namespace std;

ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

int N, M;
int maxarea;
int A[1001][2002], P[1001][2002];
stack<int> ST;

void pscpld()
{
    for (int i = 1; i <= N; ++i)
    {
        int best = 0;
        for (int j = 1; j <= M; ++j)
        {
            if (best + P[i][best] >= j)
                P[i][j] = min(best + P[i][best] - j, P[i][2 * best - j]);
            while (j - P[i][j] - 1 > 0 && j + P[i][j] + 1 <= M && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
                ++P[i][j];
            if (j + P[i][j] >= best + P[i][best])
                best = j;
        }
    }
}

int main()
{
    fin >> N >> M;
    M = 2 * M + 1;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            if (j % 2 == 1) A[i][j] = -1;
            else            fin >> A[i][j];
        }

    pscpld();

    for (int j = 2; j <= M; j += 2)
    {
        int left, right;
        for (int i = 1; i <= N; ++i)
        {
            while (!ST.empty() && P[i][j] <= P[ST.top()][j])
            {
                left = ST.top();
                right = i;

                maxarea = max(maxarea, P[i][j] * (right - left + 1));

                ST.pop();
            }
            ST.push(i);
        }
    }

    fout << maxarea << '\n';

    fin.close();
    fout.close();
    return 0;
}