Cod sursa(job #1156450)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 27 martie 2014 17:51:49
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <stack>
using namespace std;

const int MAX_N = 1002;

int N, M, sol;
int A[MAX_N][MAX_N], D[MAX_N][MAX_N];

void Manacher(int n, int v[], int d[]) {
    for(int i = 1, C = 0, R = 0; i <= n; ++i) {
        if(R >= i) {
            int i_mirror = 2 * C - i;
            d[i] = min(d[i_mirror], R - i);
        }
        while(i - d[i] - 1 >= 1 && i + d[i] + 1 <= n && v[i - d[i] - 1] == v[i + d[i] + 1])
            ++d[i];
        
        if(i + d[i] > R)
            C = i, R = i + d[i];
    }

    for(int i = 1; i <= n; ++i)
        d[i] = 2 * d[i] + 1;
}

int solveLine(int n, int v[]) {
    stack < int > st;
    int L[MAX_N], R[MAX_N];

    for(int i = 0; i < MAX_N; ++i)
        L[i] = R[i] = 0;

    for(int i = 1; i <= n; ++i) {
        while(!st.empty() && v[i] <= v[st.top()])
            st.pop();

        if(!st.empty()) 
            L[i] = st.top();
        
        st.push(i);
    }
    
    while(!st.empty())
        st.pop();

    for(int i = n; i >= 1; --i) {
        while(!st.empty() && v[i] <= v[st.top()])
            st.pop();

        if(!st.empty())
            R[i] = st.top();
        else R[i] = n + 1;
        
        st.push(i);
    }
    
    int ret = 0;
    for(int i = 1; i <= n; ++i)
        ret = max(ret, v[i] * (R[i] - L[i] - 1));

    return ret;
}

int main() {
    ifstream f("dreptpal.in");
    ofstream g("dreptpal.out");

    f >> N >> M;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            f >> A[i][j];

    for(int i = 1; i <= N; ++i)
        Manacher(M, A[i], D[i]);

    
    int temp[MAX_N];
    for(int j = 1; j <= M; ++j) {
        for(int i = 1; i <= N; ++i)
            temp[i] = D[i][j];
        sol = max(sol, solveLine(N, temp));
    }

    g << sol << "\n";

    f.close();
    g.close();

    return 0;
}