Cod sursa(job #2316766)

Utilizator mirunazMiruna Zavelca mirunaz Data 12 ianuarie 2019 13:22:37
Problema DreptPal Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>
#include <stack>
using namespace std;

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

    int n, m;
    in >> n >> m;
    int a[n][m], v[n][m];

    for (int k = 0; k < n; k ++) {
        for (int i = 0; i < m; i++) {
            in >> a[k][i];
        }

        //Manacher
        int j, centru = 0, dr = 0;
        for (int i = 0; i < m; i++) {
            if (dr <= i) {
                v[k][i] = 1;
                j = 1;

                while (i - j >= 0 && i + j < m && a[k][i - j] == a[k][i + j]) {
                    j++;
                    v[k][i]++;
                }

                dr = i + j - 1;
                centru = i;
            } else {
                v[k][i] = min(dr - i + 1, v[k][2 * centru - i]);

                if (v[k][i] + i - 1 >= dr) {
                    j = v[k][i];
                    while (i - j >= 0 && i + j < m && a[k][i - j] == a[k][i + j]) {
                        j++;
                        v[k][i]++;
                    }

                    dr = i + j - 1;
                    centru = i;
                }
            }
        }
    }

    //Skyline
    int sol = 0;
    for (int j = 0; j < m; j ++) {
        stack <int> s, first;

        int p[n];
        for (int i = 0; i < n; i ++) {
            while (!s.empty() && s.top() > v[i][j]) {
                s.pop();
                first.pop();
            }

            if (s.empty()) {
                s.push(v[i][j]);
                first.push(0);
            } else if (s.top() < v[i][j]) {
                    s.push(v[i][j]);
                    first.push(i);
            }

            p[i] = (2 * s.top() - 1) * (i - first.top() + 1);
        }

        while(!s.empty()) {
            s.pop();
        }

        while(!first.empty()) {
            first.pop();
        }

        for (int i = n - 1; i >= 0; i --) {
            while (!s.empty() && s.top() > v[i][j]) {
                s.pop();
                first.pop();
            }

            if (s.empty()) {
                s.push(v[i][j]);
                first.push(n - 1);
            } else if (s.top() < v[i][j]) {
                s.push(v[i][j]);
                first.push(i);
            }

            int x = (2 * s.top() - 1) * (first.top() - i + 1);
            p[i] = max(x, p[i]);

            if (p[i] > sol) {
                sol = p[i];
            }
        }
    }

    out << sol;

    return 0;
}