Cod sursa(job #2670875)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 10 noiembrie 2020 20:19:06
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <bits/stdc++.h>
#define DIM 1010
#define INF 2000000000
using namespace std;
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};


int a[DIM][DIM],p[DIM][DIM*2],v[DIM*2],st[DIM],dr[DIM];
deque <int> d;
int n,m,i,j;

void manacher (int a[], int p[]){
    int i, n = 0;
    v[++n] = INF;
    for (i=1;i<=m;++i){
        v[++n] = a[i];
        v[++n] = INF;
    }

    int Left = 0, Right = 0, c = 0;

    for (i=1;i<=n;++i){
        if (i > Right){

            Left = Right = c = i;
            p[i] = 1;

            while (Left - 1 >= 1 && Right + 1 <= n && v[Left-1] == v[Right+1]){
                p[i]++;
                Left--, Right++;
            }

        } else {
            int mirror = c - (i - c);
            p[i] = min (p[mirror], Right - i + 1);

            int st = i - p[i], dr = i + p[i];
            while (st >= 1 && dr <= n && v[st] == v[dr]){
                st--, dr++;
                p[i]++;
            }

            if (i - p[i] + 1 < Left){
                Left = i - p[i] + 1;
                Right = i + p[i] - 1;
                c = i;
            }}}}

int main (){

    InParser cin ("dreptpal.in");
    ofstream cout ("dreptpal.out");

    cin>>n>>m;
    for (i=1;i<=n;++i){
        for (j=1;j<=m;++j)
            cin>>a[i][j];

        manacher(a[i],p[i]);
    }

    int sol = 0;
    for (j=1;j<=m;++j){

        for (i=1;i<=n;++i)
            v[i] = p[i][2*j] - 1;

        d.clear();
        for (i=1;i<=n;++i){
            while (!d.empty() && v[i] <= v[d.back()])
                d.pop_back();

            if (d.empty())
                st[i] = 1;
            else st[i] = d.back() + 1;

            d.push_back(i);
        }

        d.clear();
        for (i=n;i;--i){
            while (!d.empty() && v[i] <= v[d.back()])
                d.pop_back();

            if (d.empty())
                dr[i] = n;
            else dr[i] = d.back() - 1;

            d.push_back(i);
        }

        for (i=1;i<=n;++i)
            sol = max (sol,(dr[i] - st[i] + 1)*v[i] );

    }

    cout<<sol;




    return 0;
}