Cod sursa(job #2458304)

Utilizator Iulia25Hosu Iulia Iulia25 Data 20 septembrie 2019 10:25:52
Problema DreptPal Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <deque>

using namespace std;

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

int n, m, k, Max;
int v[1005];
int a[1005][1005];

deque <int> s;

int main()  {
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)  {
		for (int j = 1; j <= m; ++j)  {
			fin >> v[j];
		}
		int mij = 0, r = 0;
		for (int j = 1; j <= m; ++j)  {
			if (j < r)  {
				if (a[i][mij - (j - mij)] + j < r)
					a[i][j] = a[i][mij - (j - mij)];
				else  {
					int x = r - j;
					while (v[j + x] == v[j - x] && j + x <= m && j - x >= 1)
						++x;
					--x;
					mij = j;
					r = j + x;
					a[i][j] = x;
				}
			} else  {
				int x = 1;
				while (v[j + x] == v[j - x] && j + x <= m && j - x >= 1)
					++x;
				--x;
				mij = j;
				r = j + x;
				a[i][j] = x;
			}
			a[i][j] = 2 * a[i][j] + 1;
		}
	}
	for (int j = 1; j <= m; ++j)  {
    for (int i = 1; i <= n; ++i)  {
      while (!s.empty() && a[s.back()][j] > a[i][j])  {
        k = s.back();
        if (a[k][j] * (i - k) > Max)
          Max = a[k][j] * (i - k);
        s.pop_back();
      }
      s.push_back(i);
    }
    while (!s.empty())  {
      k = s.back();
      if (a[k][j] * (n - k + 1) > Max)
        Max = a[k][j] * (n - k + 1);
      s.pop_back();
    }
  }
  fout << Max;
	return 0;
}