Cod sursa(job #2465369)

Utilizator Iulia25Hosu Iulia Iulia25 Data 30 septembrie 2019 00:21:49
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <deque>

using namespace std;

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

int n, m, ans, val, r, mij;
int v[1005];
int a[1005][1005];

deque <pair <int, int>> s;

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