Cod sursa(job #1518560)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 5 noiembrie 2015 23:06:51
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

int bf_extend(vector < int> const &V, int i, int dist) {
    int j;
    for(j = dist; 1 <= i - j && i + j < V.size() && V[i + j] == V[i - j]; j++);
    return j - 1;
}

vector < int > manacher(vector < int > const &V) {
    vector < int > len(V.size(), 0);
    int i, j, r, ir;

    for(i = 1, r = ir = -1; i < V.size(); i++) {
        if(i > r) {
            len[i] = bf_extend(V, i, 1);
        }
        else {
            if(i + len[2*ir - i] < r) {
                len[i] = len[2*ir - i];
            }
            else {
                len[i] = bf_extend(V, i, r - i + 1);
            }
        }
    }
    return len;
}

int get_area_column(vector < int > const &col) {
    vector < int > l(col.size()), r(col.size());
    stack < int > s;
    int i, amax = 0;

    /*for(i = 1; i < col.size(); i++) out << col[i] << ' ';
    out << '\n';*/

    for(i = 1; i < col.size(); i++) {
        while(!s.empty() && col[i] < col[s.top()]) {
            r[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()) {
        r[s.top()] = col.size();
        s.pop();
    }

    for(i = col.size() - 1; i; i--) {
        while(!s.empty() && col[i] < col[s.top()]) {
            l[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()) {
        l[s.top()] = 0;
        s.pop();
    }

    for(i = 1; i < col.size(); i++) {
        amax = max(amax, (2*col[i] + 1) * (r[i] - l[i] - 1));
    }
    return amax;
}

int get_area_whole(const int n, const int m, vector < vector < int > > const &len) {
    vector < int > col;
    int amax = 0, i, j;
    for(i = 1; i <= m; i++) {
        col.clear();
        col.push_back(0);
        for(j = 1; j <= n; j++) {
            col.push_back(len[j][i]);
        }
        //out << get_area_column(col) << '\n';
        amax = max(amax, get_area_column(col));
    }
    return amax;
}

int main() {
    int n, m, i, j;

    in >> n >> m;
    vector < vector < int > > a(n + 1), len(n + 1);
    for(i = 1; i <= n; i++) {
        a[i].resize(m + 1);
        len[i].resize(m + 1);
        for(j = 1; j <= m; j++) {
            in >> a[i][j];
        }
        len[i] = manacher(a[i]);
    }

    /*for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            out << len[i][j] << ' ';
        }
        out << '\n';
    }*/

    out << get_area_whole(n, m, len) << '\n';
    return 0;
}