Cod sursa(job #638510)

Utilizator SpiderManSimoiu Robert SpiderMan Data 20 noiembrie 2011 21:56:32
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
# include <cstdio>
# include <stack>
using namespace std;

const char *FIN = "dreptpal.in", *FOU = "dreptpal.out";
const int MAX = 1005;

struct vec {
    int val, nr;
    vec () {};
    vec (int a, int b) {
        val = a, nr = b;
    }
};

stack <vec> st;
int N, M, sol, A[MAX][MAX << 1], V[MAX][MAX];

inline int min (int a, int b) {
    return a < b ? a : b;
}

inline int max (int a, int b) {
    return a > b ? a : b;
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            scanf ("%d", V[i] + j);
    for (int i = 1; i <= N; ++i) {
        int st = 1, dr = 1;
        for (int j = 2; j <= M; ++j)
            if (j <= dr) {
                A[i][j] = min (A[i][st + dr - j], dr - j);
                if (j + A[i][j] == dr)
                    for (st = j - A[i][j], dr = j + A[i][j]; st > 1 && dr < M && V[i][st - 1] == V[i][dr + 1]; --st, ++dr)
                        A[i][j] += 1;
            } else {
                for (st = dr = j; st > 1 && dr < M && V[i][st - 1] == V[i][dr + 1]; --st, ++dr)
                    A[i][j] += 1;
            }
    }
    for (int j = 1; j <= M; ++j) {
        for (int i = 1; i <= N; ++i) {
            int mini = 0;
            for (; st.size () && A[i][j] <= st.top ().val; st.pop ())
                sol = max (sol, (st.top ().val << 1 | 1) * (mini += st.top ().nr));
            st.push (vec (A[i][j], ++mini));
        }
        int mini = 0;
        for (; st.size (); st.pop ())
            sol = max (sol, (st.top ().val << 1 | 1) * (mini += st.top ().nr));
    }

    fprintf (fopen (FOU, "w"), "%d", sol);
}